{"id":26357,"date":"2017-10-26T21:11:23","date_gmt":"2017-10-26T15:41:23","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26357"},"modified":"2017-10-26T21:11:23","modified_gmt":"2017-10-26T15:41:23","slug":"greedy-algorithms-set-2-kruskals-minimum-spanning-tree-algorithm-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-algorithm-2\/","title":{"rendered":"Greedy Algorithms | Set 2 (Kruskal\u2019s Minimum Spanning Tree Algorithm)"},"content":{"rendered":"

What is Minimum Spanning Tree?<\/em>
\nGiven a connected and undirected graph, a spanning tree<\/em> of that graph is a subgraph that is a tree and connects all the vertices together. <\/span>A single graph can have many different spanning trees. A minimum spanning tree (MST)<\/em> or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.<\/p>\n

How many edges does a minimum spanning tree has?<\/em>
\nA minimum spanning tree has (V \u2013 1) edges where V is the number of vertices in the given graph.<\/p>\n

What are the applications of Minimum Spanning Tree?<\/em>
\nSee this <\/a>for applications of MST.<\/p>\n[ad type=”banner”]\n

Below are the steps for finding MST using Kruskal\u2019s algorithm:<\/p>\n

1.<\/strong> Sort all the edges in non-decreasing order of their weight.\r\n\r\n2.<\/strong> Pick the smallest edge. Check if it forms a cycle with the spanning tree \r\nformed so far. If cycle is not formed, include this edge. Else, discard it.  \r\n\r\n3.<\/strong> Repeat step#2 until there are (V-1) edges in the spanning tree.<\/pre>\n
The step#2 uses Union-Find algorithm<\/a> to detect cycle. So we recommend to read following post as a prerequisite.
\nUnion-Find Algorithm | Set 1 (Detect Cycle in a Graph)<\/a>
\nUnion-Find Algorithm | Set 2 (Union By Rank and Path Compression)<\/a><\/p>\n
The algorithm is a Greedy Algorithm. The Greedy Choice is to pick the smallest weight edge that does not cause a cycle in the MST constructed so far. Let us understand it with an example: Consider the below input graph.<\/p>\n
\"Kruskal\u2019s<\/p>\n
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having (9 \u2013 1) = 8 edges.<\/p>\n
After sorting:\r\nWeight   Src    Dest\r\n1         7      6\r\n2         8      2\r\n2         6      5\r\n4         0      1\r\n4         2      5\r\n6         8      6\r\n7         2      3\r\n7         7      8\r\n8         0      7\r\n8         1      2\r\n9         3      4\r\n10        5      4\r\n11        1      7\r\n14        3      5<\/pre>\n
1.<\/strong> Pick edge 7-6:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
2.<\/strong> Pick edge 8-2:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
3.<\/strong> Pick edge 6-5:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
4.<\/strong> Pick edge 0-1:<\/em> No cycle is formed, include it<\/p>\n
\"Kruskal\u2019s<\/p>\n
5.<\/strong> Pick edge 2-5:<\/em> No cycle is formed, include it.<\/p>\n
6.<\/strong> Pick edge 8-6: <\/em>Since including this edge results in cycle, discard it.<\/p>\n
7.<\/strong> Pick edge 2-3:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
8.<\/strong> Pick edge 7-8:<\/em> Since including this edge results in cycle, discard it.<\/p>\n
9.<\/strong> Pick edge 0-7:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
10.<\/strong> Pick edge 1-2: <\/em>Since including this edge results in cycle, discard it.<\/p>\n
11.<\/strong> Pick edge 3-4:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
 <\/p>\n
Python programming:<\/p>\n
 
 <\/div> 
# Python program for Kruskal's algorithm to find Minimum Spanning Tree# of a given connected, undirected and weighted graph from collections import defaultdict #Class to represent a graphclass Graph:     def __init__(self,vertices):        self.V= vertices #No. of vertices        self.graph = [] # default dictionary to store graph               # function to add an edge to graph    def addEdge(self,u,v,w):        self.graph.append([u,v,w])     # A utility function to find set of an element i    # (uses path compression technique)    def find(self, parent, i):        if parent[i] == i:            return i        return self.find(parent, parent[i])     # A function that does union of two sets of x and y    # (uses union by rank)    def union(self, parent, rank, x, y):        xroot = self.find(parent, x)        yroot = self.find(parent, y)         # Attach smaller rank tree under root of high rank tree        # (Union by Rank)        if rank[xroot] < rank[yroot]:            parent[xroot] = yroot        elif rank[xroot] > rank[yroot]:            parent[yroot] = xroot        #If ranks are same, then make one as root and increment        # its rank by one        else :            parent[yroot] = xroot            rank[xroot] += 1     # The main function to construct MST using Kruskal's algorithm    def KruskalMST(self):         result =[] #This will store the resultant MST         i = 0 # An index variable, used for sorted edges        e = 0 # An index variable, used for result[]         #Step 1:  Sort all the edges in non-decreasing order of their        # weight.  If we are not allowed to change the given graph, we        # can create a copy of graph        self.graph =  sorted(self.graph,key=lambda item: item[2])        #print self.graph         parent = [] ; rank = []         # Create V subsets with single elements        for node in range(self.V):            parent.append(node)            rank.append(0)             # Number of edges to be taken is equal to V-1        while e < self.V -1 :             # Step 2: Pick the smallest edge and increment the index            # for next iteration            u,v,w =  self.graph[i]            i = i + 1            x = self.find(parent, u)            y = self.find(parent ,v)             # If including this edge does't cause cycle, include it            # in result and increment the index of result for next edge            if x != y:                e = e + 1                  result.append([u,v,w])                self.union(parent, rank, x, y)                      # Else discard the edge         # print the contents of result[] to display the built MST        print "Following are the edges in the constructed MST"        for u,v,weight  in result:            #print str(u) + " -- " + str(v) + " == " + str(weight)            print ("%d -- %d == %d" % (u,v,weight))  g = Graph(4)g.addEdge(0, 1, 10)g.addEdge(0, 2, 6)g.addEdge(0, 3, 5)g.addEdge(1, 3, 15)g.addEdge(2, 3, 4) g.KruskalMST()<\/code><\/pre> <\/div>\n
<\/code><\/code><\/div>\n
Following are the edges in the constructed MST\r\n2 -- 3 == 4\r\n0 -- 3 == 5\r\n0 -- 1 == 10<\/pre>\n
Time Complexity:<\/strong> O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost O(V2<\/sup>), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Kruskal\u2019s Minimum Spanning Tree Algorithm) – Minimum Spanning Tree A single graph can have many different spanning trees. A minimum spanning tree (MST).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,76379],"tags":[70774,78372,70781,78371,78374,78373,70770,70804],"class_list":["post-26357","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-minimum-spanning-tree","tag-kruskals-algorithm-c","tag-kruskals-algorithm-geeksforgeeks","tag-kruskals-algorithm-in-c","tag-kruskals-algorithm-java","tag-kruskals-algorithm-pseudocode","tag-kruskals-algorithm-time-complexity","tag-prims-algorithm-example","tag-prims-algorithm-minimum-spanning-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26357","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26357"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26357\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}