{"id":337,"date":"2016-12-15T22:27:14","date_gmt":"2016-12-15T14:27:14","guid":{"rendered":"http:\/\/blog.messi.moe\/?p=337"},"modified":"2017-01-29T17:24:46","modified_gmt":"2017-01-29T09:24:46","slug":"graph-bfs-dfs-and-minimum-spanning-tree","status":"publish","type":"post","link":"https:\/\/blog.messi.moe\/?p=337","title":{"rendered":"Basic Graph Algorithms"},"content":{"rendered":"<pre><code class=\"python\"># Graph Algorithms\n\ndef isGraph(edge):\n    a=len(edge)\n    for i in edge:\n        if len(i)!=a:\n            return False\n    return True\n\ndef findMatrixMin(edge):\n    row=999999\n    col=999999\n    MIN=999999\n    for i in range(len(edge)):\n        for j in range(len(edge)):\n            if edge[i][j]&lt;MIN and edge[i][j]!=0:\n                MIN=edge[i][j]\n                row=i+1 \n                col=j+1 \n    return MIN,[row,col]\n\n#print findMatrixMin(edge)\n\nclass graph:\n    edge=None \n    v=0\n    visited=[]\n    def __init__(self,edge):\n        if isGraph(edge)==True:\n            self.edge=[]\n            for i in edge:\n                newlist=i[:]\n                self.edge.append(newlist)\n\n            self.v=len(edge)\n            self.visited=[0]*self.v \n        else:\n            raise \"Error!\"\n    def addVertex(self,contact):\n        if len(contact)==self.v:\n            for i in range(len(contact)):\n                self.edge[i].append(contact[i])\n            contact.append(0)\n            self.edge.append(contact)\n            v=v+1\n        else:\n            raise \"Error!\"\n    def delVertex(self,vnum):\n        # vnum=1~v \n        if vnum&gt;=1 and vnum&lt;=self.v:\n            self.edge.pop(vnum-1)\n            for i in self.edge:\n                i.pop(vnum-1)\n        else:\n            raise \"Error!\"\n    def viewGraph(self):\n        for i in self.edge:\n            print i \n    def cutEdge(self,v1,v2):\n        # v1,v2=1~v \n        self.edge[v1-1][v2-1]=0\n        self.edge[v2-1][v1-1]=0\n    def DFS(self,root):\n        # root=1~v\n        if root&gt;=1 and root&lt;=self.v:\n            self.visited[root-1]=1\n            print root,\n            for i in range(self.v):\n                if self.edge[root-1][i]!=0 and self.visited[i]==0:\n                        self.DFS(i+1)\n        else:\n            raise \"Error!\"\n    def DFS_nr(self,root):\n        # root=1~v \n        # Non-recursive\n        stack=[]\n        result=[]\n        if root&gt;=1 and root&lt;=self.v:\n            stack.append(root)\n            while stack!=[]:\n                peek=stack.pop()\n                if self.visited[peek-1]==0:\n                    result.append(peek)\n                    self.visited[peek-1]=1 \n                for i in range(self.v):\n                    if self.edge[peek-1][self.v-1-i]!=0 and self.visited[self.v-1-i]==0:\n                        stack.append(self.v-i)\n        else:\n            raise \"Error!\"\n        return result\n    def BFS_nr(self,root):\n        # root=1~v\n        # Non-recursive\n        queue=[]\n        result=[]\n        if root&gt;=1 and root&lt;=self.v:\n            queue.append(root)\n            self.visited[root-1]=1 \n            while queue!=[]:\n                node=queue.pop(0)\n                result.append(node)\n                for i in range(self.v):\n                    if self.edge[node-1][i]!=0 and self.visited[i]==0:\n                        self.visited[i]=1 \n                        queue.append(i+1)\n        else:\n            raise \"Error!\"\n        return result\n    def Kruskal(self):\n        if self.v&lt;=1:\n            return 0,None \n        def findSet(element,forest):\n            for i in forest:\n                if i!=None:\n                    if element in i:\n                        return i \n            return None\n        forest=[]\n        for i in range(self.v):\n            forest.append([i+1])\n        minST=0\n        minEdges=[]\n        while len(forest)&gt;1:\n            m,[v1,v2]=findMatrixMin(self.edge)\n            set1=findSet(v1,forest)\n            set2=findSet(v2,forest)\n            #print m,set1,set2\n            if set1!=set2:\n                self.edge[v1-1][v2-1]=0\n                self.edge[v2-1][v1-1]=0\n                minST+=m \n                minEdges.append([v1,v2])\n                newTree=set1+set2\n                forest.remove(set1)\n                forest.remove(set2)\n                forest.append(newTree)\n        return minST,minEdges\n    def Prim(self):\n        if self.v&lt;=1:\n            return 0,None \n        minEdges=[]\n        minST=0\n        notInTree=[]\n        prim=[]\n        for i in range(self.v):\n            notInTree.append(i+1)\n        # start with node 1 \n        notInTree.remove(1)\n        prim.append(1)\n        while notInTree:\n            minEdge=[999999,999999]\n            minL=999999\n            for i in prim:\n                for j in notInTree:\n                    if self.edge[i-1][j-1]&lt;minL and self.edge[i-1][j-1]!=0:\n                        minL=self.edge[i-1][j-1]\n                        minEdge=[i,j]\n            minST+=minL\n            minEdges.append(minEdge)\n            prim.append(minEdge[1])\n            notInTree.remove(minEdge[1])\n        return minST,minEdges\n    def Floyd_Warshall(self):\n        dist=self.edge \n        for i in range(self.v):\n            for j in range(self.v):\n                if dist[i][j]==0:\n                    dist[i][j]=999999\n        for i in range(self.v):\n            dist[i][i]=0\n        for k in range(self.v):\n            for i in range(self.v):\n                for j in range(self.v):\n                    if dist[i][j]&gt;dist[i][k]+dist[k][j]:\n                        dist[i][j]=dist[i][k]+dist[k][j]\n        return dist\n    def Dijkstra(self,s):\n        dist=self.edge \n        result=[999999]*self.v \n        result[s-1]=0\n        for i in range(self.v):\n            for j in range(self.v):\n                if i!=j and dist[i][j]==0:\n                    dist[i][j]=999999\n        S=[]\n        U=[]\n        for i in range(self.v):\n            U.append(i+1)\n        while U!=[]:\n            MIN=999999\n            index=0\n            for i in S:\n                for j in U:\n                    dist[s-1][j-1]=min(dist[s-1][j-1],dist[s-1][i-1]+dist[i-1][j-1])\n            for j in U:\n                if dist[s-1][j-1]&lt;MIN:\n                    MIN=dist[s-1][j-1]\n                    index=j\n            S.append(index)\n            U.remove(index)\n        return dist[s-1]\n\nedge=[[0,3,2,4,0,0,0],\n      [3,0,4,0,0,0,6],\n      [2,4,0,0,0,1,0],\n      [4,0,0,0,5,0,0],\n      [0,0,0,5,0,3,0],\n      [0,0,1,0,3,0,2],\n      [0,6,0,0,0,2,0]]\n# 0 3 2 4 0 0 0\n# 3 0 4 0 0 0 6\n# 2 4 0 0 0 0 1\n# 4 0 0 0 5 0 0\n# 0 0 0 5 0 3 0\n# 0 0 1 0 3 0 2\n# 0 6 0 0 0 2 0    \n\nGraph=graph(edge)\nprint Graph.DFS_nr(1)\nGraph=graph(edge)\nprint Graph.BFS_nr(1)\nGraph=graph(edge)\nminST,minEdges=Graph.Kruskal()\nprint \"Kruskal:\",minEdges,\"  Min:\",minST\nGraph=graph(edge)\nminST,minEdges=Graph.Prim()\nprint \"Prim:\",minEdges,\"  Min:\",minST\nGraph=graph(edge)\ndist=Graph.Floyd_Warshall()\nfor i in dist:\n    print i \nGraph=graph(edge)\nprint \"Dijstrak(1):\",Graph.Dijkstra(1)\n<\/code><\/pre>\n<pre><code class=\"bash\">Python 2.7.10 (default, Jul 14 2015, 19:46:27)\n[GCC 4.8.2] on linux\n\n[1, 2, 3, 6, 5, 4, 7]\n[1, 2, 3, 4, 7, 6, 5]\nKruskal: [[3, 6], [1, 3], [6, 7], [1, 2], [5, 6], [1, 4]]   Min: 15\nPrim: [[1, 3], [3, 6], [6, 7], [1, 2], [6, 5], [1, 4]]   Min: 15\n[0, 3, 2, 4, 6, 3, 5]\n[3, 0, 4, 7, 8, 5, 6]\n[2, 4, 0, 6, 4, 1, 3]\n[4, 7, 6, 0, 5, 7, 9]\n[6, 8, 4, 5, 0, 3, 5]\n[3, 5, 1, 7, 3, 0, 2]\n[5, 6, 3, 9, 5, 2, 0]\nDijstrak(1): [0, 3, 2, 4, 6, 3, 5]\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<pre><code class=\"python\"># Graph Algorithms\n\ndef isGraph(edge):\n    a=len(edge)\n    for i in edge:\n        if len(i)!=a:\n            return False\n    return True\n\ndef findMatrixMin(edge):\n    row=999999\n    col=999999\n    MIN=999999\n    for i in range(len(edge)):\n        for j in range(len(edge)):\n            if edge[i][j]&lt;MIN and edge[i][j]!=0:\n                MIN=edge[i][j]\n                row=i+1 \n                col=j+1 \n    return MIN,[row,col]\n\n#print findMatrixMin(edge)\n\nclass graph:\n    edge=None \n    v=0\n    visited=[]\n    def __init__(self,edge):\n        if isGraph(edge)==True:\n            self.edge=[]\n            for i in edge:\n                newlist=i[:]\n                self.edge.append(newlist)\n\n            self.v=len(edge)\n            self.visited=[0]*self.v \n        else:\n            raise \"Error!\"\n    def addVertex(self,contact):\n        if len(contact)==self.v:\n            for i in range(len(contact)):\n                self.edge[i].append(contact[i])\n            contact.append(0)\n            self.edge.append(contact)\n            v=v+1\n        else:\n            raise \"Error!\"\n    def delVertex(self,vnum):\n        # vnum=1~v \n        if vnum&gt;=1 and vnum&lt;=self.v:\n            self.edge.pop(vnum-1)\n            for i in self.edge:\n                i.pop(vnum-1)\n        else:\n            raise \"Error!\"\n    def viewGraph(self):\n        for i in self.edge:\n            print i \n    def cutEdge(self,v1,v2):\n        # v1,v2=1~v \n        self.edge[v1-1][v2-1]=0\n        self.edge[v2-1][v1-1]=0\n    def DFS(self,root):\n        # root=1~v\n        if root&gt;=1 and root&lt;=self.v:\n            self.visited[root-1]=1\n            print root,\n            for i in range(self.v):\n                if self.edge[root-1][i]!=0 and self.visited[i]==0:\n                        self.DFS(i+1)\n        else:\n            raise \"Error!\"\n    def DFS_nr(self,root):\n        # root=1~v \n        # Non-recursive\n        stack=[]\n        result=[]\n        if root&gt;=1 and root&lt;=self.v:\n            stack.append(root)\n            while stack!=[]:\n                peek=stack.pop()\n                if self.visited[peek-1]==0:\n                    result.append(peek)\n                    self.visited[peek-1]=1 \n                for i in range(self.v):\n                    if self.edge[peek-1][self.v-1-i]!=0 and self.visited[self.v-1-i]==0:\n                        stack.append(self.v-i)\n        else:\n            raise \"Error!\"\n        return result\n    def BFS_nr(self,root):\n        # root=1~v\n        # Non-recursive\n        queue=[]\n        result=[]\n        if root&gt;=1 and root&lt;=self.v:\n            queue.append(root)\n            self.visited[root-1]=1 \n            while queue!=[]:\n                node=queue.pop(0)\n                result.append(node)\n                for i in range(self.v):\n                    if self.edge[node-1][i]!=0 and self.visited[i]==0:\n                        self.visited[i]=1 \n                        queue.append(i+1)\n        else:\n            raise \"Error!\"\n        return result\n    def Kruskal(self):\n        if self.v&lt;=1:\n            return 0,None \n        def findSet(element,forest):\n            for i in forest:\n                if i!=None:\n                    if element in i:\n                        return i \n            return None\n        forest=[]\n        for i in range(self.v):\n            forest.append([i+1])\n        minST=0\n        minEdges=[]\n        while len(forest)&gt;1:\n            m,[v1,v2]=findMatrixMin(self.edge)\n            set1=findSet(v1,forest)\n            set2=findSet(v2,forest)\n            #print m,set1,set2\n            if set1!=set2:\n                self.edge[v1-1][v2-1]=0\n                self.edge[v2-1][v1-1]=0\n                minST+=m \n                minEdges.append([v1,v2])\n                newTree=set1+set2\n                forest.remove(set1)\n                forest.remove(set2)\n                forest.append(newTree)\n        return minST,minEdges\n    def Prim(self):\n        if self.v&lt;=1:\n            return 0,None \n        minEdges=[]\n        minST=0\n        notInTree=[]\n        prim=[]\n        for i in range(self.v):\n            notInTree.append(i+1)\n        # start with node 1 \n        notInTree.remove(1)\n        prim.append(1)\n        while notInTree:\n            minEdge=[999999,999999]\n            minL=999999\n            for i in prim:\n                for j in notInTree:\n                    if self.edge[i-1][j-1]&lt;minL and self.edge[i-1][j-1]!=0:\n                        minL=self.edge[i-1][j-1]\n                        minEdge=[i,j]\n            minST+=minL\n            minEdges.append(minEdge)\n            prim.append(minEdge[1])\n            notInTree.remove(minEdge[1])\n        return minST,minEdges\n    def Floyd_Warshall(self):\n        dist=self.edge \n        for i in range(self.v):\n            for j in range(self.v):\n                if dist[i][j]==0:\n                    dist[i][j]=999999\n        for i in range(self.v):\n            dist[i][i]=0\n        for k in range(self.v):\n            for i in range(self.v):\n                for j in range(self.v):\n                    if dist[i][j]&gt;dist[i][k]+dist[k][j]:\n                        dist[i][j]=dist[i][k]+dist[k][j]\n        return dist\n    def Dijkstra(self,s):\n        dist=self.edge \n        result=[999999]*self.v \n        result[s-1]=0\n        for i in range(self.v):\n            for j in range(self.v):\n                if i!=j and dist[i][j]==0:\n                    dist[i][j]=999999\n        S=[]\n        U=[]\n        for i in range(self.v):\n            U.append(i+1)\n        while U!=[]:\n            MIN=999999\n            index=0\n            for i in S:\n                for j in U:\n                    dist[s-1][j-1]=min(dist[s-1][j-1],dist[s-1][i-1]+dist[i-1][j-1])\n            for j in U:\n                if dist[s-1][j-1]&lt;MIN:\n                    MIN=dist[s-1][j-1]\n                    index=j\n            S.append(index)\n            U.remove(index)\n        return dist[s-1]\n\nedge=[[0,3,2,4,0,0,0],\n      [3,0,4,0,0,0,6],\n      [2,4,0,0,0,1,0],\n      [4,0,0,0,5,0,0],\n      [0,0,0,5,0,3,0],\n      [0,0,1,0,3,0,2],\n      [0,6,0,0,0,2,0]]\n# 0 3 2 4 0 0 0\n# 3 0 4 0 0 0 6\n# 2 4 0 0 0 0 1\n# 4 0 0 0 5 0 0\n# 0 0 0 5 0 3 0\n# 0 0 1 0 3 0 2\n# 0 6 0 0 0 2 0    \n\nGraph=graph(edge)\nprint Graph.DFS_nr(1)\nGraph=graph(edge)\nprint Graph.BFS_nr(1)\nGraph=graph(edge)\nminST,minEdges=Graph.Kruskal()\nprint \"Kruskal:\",minEdges,\"  Min:\",minST\nGraph=graph(edge)\nminST,minEdges=Graph.Prim()\nprint \"Prim:\",minEdges,\"  Min:\",minST\nGraph=graph(edge)\ndist=Graph.Floyd_Warshall()\nfor i in dist:\n    print i \nGraph=graph(edge)\nprint \"Dijstrak(1):\",Graph.Dijkstra(1)\n<\/code><\/pre>\n<pre><code class=\"bash\">Python 2.7.10 (default, Jul 14 2015, 19:46:27)\n[GCC 4.8.2] on linux\n\n[1, 2, 3, 6, 5, 4, 7]\n[1, 2, 3, 4, 7, 6, 5]\nKruskal: [[3, 6], [1, 3], [6, 7], [1, 2], [5, 6], [1, 4]]   Min: 15\nPrim: [[1, 3], [3, 6], [6, 7], [1, 2], [6, 5], [1, 4]]   Min: 15\n[0, 3, 2, 4, 6, 3, 5]\n[3, 0, 4, 7, 8, 5, 6]\n[2, 4, 0, 6, 4, 1, 3]\n[4, 7, 6, 0, 5, 7, 9]\n[6, 8, 4, 5, 0, 3, 5]\n[3, 5, 1, 7, 3, 0, 2]\n[5, 6, 3, 9, 5, 2, 0]\nDijstrak(1): [0, 3, 2, 4, 6, 3, 5]\n<\/code><\/pre>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/337"}],"collection":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=337"}],"version-history":[{"count":5,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/337\/revisions"}],"predecessor-version":[{"id":401,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/337\/revisions\/401"}],"wp:attachment":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=337"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=337"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=337"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}