Greedy_Algorithm_Kruskal_and_prim.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 - 2: 2\n",
      "2 - 5: 2\n",
      "2 - 3: 3\n",
      "3 - 4: 3\n",
      "0 - 1: 4\n"
     ]
    }
   ],
   "source": [
    "# Kruskal 알고리즘 구현하기\n",
    "\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self, vertices):\n",
    "        self.V = vertices\n",
    "        self.graph = []\n",
    "\n",
    "    def add_edge(self, u, v, w):\n",
    "        self.graph.append([u, v, w])\n",
    "\n",
    "    def find(self, parent, i):\n",
    "        if parent[i] == i:\n",
    "            return i\n",
    "        return self.find(parent, parent[i])\n",
    "\n",
    "    def apply_union(self, parent, rank, x, y):\n",
    "        xroot = self.find(parent, x)\n",
    "        yroot = self.find(parent, y)\n",
    "        if rank[xroot] < rank[yroot]:\n",
    "            parent[xroot] = yroot\n",
    "        elif rank[xroot] > rank[yroot]:\n",
    "            parent[yroot] = xroot\n",
    "        else:\n",
    "            parent[yroot] = xroot\n",
    "            rank[xroot] += 1\n",
    "\n",
    "    def kruskal_algo(self):\n",
    "        result = []\n",
    "        i, e = 0, 0\n",
    "        self.graph = sorted(self.graph, key=lambda item: item[2])\n",
    "        parent = []\n",
    "        rank = []\n",
    "        for node in range(self.V):\n",
    "            parent.append(node)\n",
    "            rank.append(0)\n",
    "        while e < self.V - 1:\n",
    "            u, v, w = self.graph[i]\n",
    "            i = i + 1\n",
    "            x = self.find(parent, u)\n",
    "            y = self.find(parent, v)\n",
    "            if x != y:\n",
    "                e = e + 1\n",
    "                result.append([u, v, w])\n",
    "                self.apply_union(parent, rank, x, y)\n",
    "        for u, v, weight in result:\n",
    "            print(\"%d - %d: %d\" % (u, v, weight))\n",
    "\n",
    "\n",
    "g = Graph(6)\n",
    "g.add_edge(0, 1, 4)\n",
    "g.add_edge(0, 2, 4)\n",
    "g.add_edge(1, 2, 2)\n",
    "g.add_edge(1, 0, 4)\n",
    "g.add_edge(2, 0, 4)\n",
    "g.add_edge(2, 1, 2)\n",
    "g.add_edge(2, 3, 3)\n",
    "g.add_edge(2, 5, 2)\n",
    "g.add_edge(2, 4, 4)\n",
    "g.add_edge(3, 2, 3)\n",
    "g.add_edge(3, 4, 3)\n",
    "g.add_edge(4, 2, 4)\n",
    "g.add_edge(4, 3, 3)\n",
    "g.add_edge(5, 2, 2)\n",
    "g.add_edge(5, 4, 3)\n",
    "g.kruskal_algo()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edge : Weight\n",
      "\n",
      "0-1:9\n",
      "1-3:19\n",
      "3-4:31\n",
      "3-2:51\n"
     ]
    }
   ],
   "source": [
    "# Prim 알고리즘\n",
    "\n",
    "INF = 9999999\n",
    "V = 5\n",
    "G = [[0, 9, 75, 0, 0],\n",
    "     [9, 0, 95, 19, 42],\n",
    "     [75, 95, 0, 51, 66],\n",
    "     [0, 19, 51, 0, 31],\n",
    "     [0, 42, 66, 31, 0]]\n",
    "selected = [0, 0, 0, 0, 0]\n",
    "no_edge = 0\n",
    "selected[0] = True\n",
    "print(\"Edge : Weight\\n\")\n",
    "\n",
    "while (no_edge < V - 1):\n",
    "    minimum = INF\n",
    "    x = 0\n",
    "    y = 0\n",
    "    for i in range(V):\n",
    "        if selected[i]:\n",
    "            for j in range(V):\n",
    "                if ((not selected[j]) and G[i][j]):  \n",
    "                    # not in selected and there is an edge\n",
    "                    if minimum > G[i][j]:\n",
    "                        minimum = G[i][j]\n",
    "                        x = i\n",
    "                        y = j\n",
    "    print(str(x) + \"-\" + str(y) + \":\" + str(G[x][y]))\n",
    "    selected[y] = True\n",
    "    no_edge += 1\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}