{"id":27533,"date":"2018-02-06T20:56:45","date_gmt":"2018-02-06T15:26:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27533"},"modified":"2018-02-06T20:56:45","modified_gmt":"2018-02-06T15:26:45","slug":"kruskals-minimum-spanning-tree-using-stl-c","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/kruskals-minimum-spanning-tree-using-stl-c\/","title":{"rendered":"Kruskal\u2019s Minimum Spanning Tree using STL in C++"},"content":{"rendered":"<p>Given an undirected, connected and weighted graph, find <strong>M<\/strong>inimum <strong>S<\/strong>panning <strong>T<\/strong>ree (MST) of the graph using Kruskal\u2019s algorithm.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-27542\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Kruskal\u2019s-Minimum-Spanning-Tree-using-STL-in-C.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree using STL in C++\" width=\"714\" height=\"333\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Kruskal\u2019s-Minimum-Spanning-Tree-using-STL-in-C.png 714w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Kruskal\u2019s-Minimum-Spanning-Tree-using-STL-in-C-300x140.png 300w\" sizes=\"(max-width: 714px) 100vw, 714px\" \/><\/p>\n<pre>Input :   Graph as an array of edges\r\nOutput :  Edges of MST are \r\n          6 - 7\r\n          2 - 8\r\n          5 - 6\r\n          0 - 1\r\n          2 - 5\r\n          2 - 3\r\n          0 - 7\r\n          3 - 4\r\n          \r\n          Weight of MST is 37\r\n\r\n<strong>Note : <\/strong> There are two possible MSTs, the other\r\n        MST includes edge 1-2 in place of 0-7.<\/pre>\n<p>We have discussed below Kruskal\u2019s MST implementations.<\/p>\n<p>Greedy Algorithms | Set 2 (Kruskal\u2019s Minimum Spanning Tree Algorithm)<\/p>\n<p>Below are the steps for finding MST using Kruskal\u2019s algorithm<\/p>\n<ol>\n<li>Sort all the edges in non-decreasing order of their weight.<\/li>\n<li>Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.<\/li>\n<li>Repeat step#2 until there are (V-1) edges in the spanning tree.<\/li>\n<\/ol>\n<p>Here are some key points which will be useful for us in implementing the Kruskal\u2019s algorithm using STL.<\/p>\n<ol>\n<li>Use a vector of edges which consist of all the edges in the graph and each item of a vector will contain 3 parameters: source, destination and the cost of an edge between the source and destination.\n<pre>vector<pair<int, pair<int, int> > > edges;<\/pre>\n<p>Here in the outer pair (i.e pair<int,pair<int,int> > ) the first element corresponds to the cost of a edge while the second element is itself a pair, and it contains two vertices of edge.<\/li>\n<li>Use the inbuilt std::sort to sort the edges in the non-decreasing order; by default the sort function sort in non-decreasing order.<\/li>\n<li>We use the Union Find Algorithm to check if it the current edge forms a cycle if it is added in the current MST. If yes discard it, else include it (union).<\/li>\n<\/ol>\n<p><strong>Pseudo Code:<\/strong><\/p>\n<pre>\/\/ Initialize result\r\nmst_weight = 0\r\n\r\n\/\/ Create V single item sets\r\n<strong>for<\/strong> <strong>each<\/strong> vertex v\r\n\tparent[v] = v;\r\n\trank[v] = 0;\r\n\r\n<strong>Sort<\/strong> all edges into non decreasing \r\norder by weight w\r\n\r\n<strong>for<\/strong> each (u, v) taken from the sorted list  E\r\n    <strong>do if<\/strong> <strong>FIND-SET<\/strong>(u) != <strong>FIND-SET<\/strong>(v)\r\n        <strong>print<\/strong> edge(u, v)\r\n        mst_weight += weight of edge(u, v)\r\n        <strong>UNION<\/strong>(u, v)<\/pre>\n<p>Below is C++ implementation of above algorithm.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20for%20Kruskal\u2019s%20algorithm%20to%20find%20Minimum%0A%2F%2F%20Spanning%20Tree%20of%20a%20given%20connected%2C%20undirected%20and%0A%2F%2F%20weighted%20graph%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Creating%20shortcut%20for%20an%20integer%20pair%0Atypedef%20%20pair%3Cint%2C%20int%3E%20iPair%3B%0A%20%0A%2F%2F%20Structure%20to%20represent%20a%20graph%0Astruct%20Graph%0A%7B%0A%20%20%20%20int%20V%2C%20E%3B%0A%20%20%20%20vector%3C%20pair%3Cint%2C%20iPair%3E%20%3E%20edges%3B%0A%20%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20Graph(int%20V%2C%20int%20E)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20%20%20%20%20this-%3EE%20%3D%20E%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Utility%20function%20to%20add%20an%20edge%0A%20%20%20%20void%20addEdge(int%20u%2C%20int%20v%2C%20int%20w)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20edges.push_back(%7Bw%2C%20%7Bu%2C%20v%7D%7D)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%20MST%20using%20Kruskal\u2019s%0A%20%20%20%20%2F%2F%20MST%20algorithm%0A%20%20%20%20int%20kruskalMST()%3B%0A%7D%3B%0A%20%0A%2F%2F%20To%20represent%20Disjoint%20Sets%0Astruct%20DisjointSets%0A%7B%0A%20%20%20%20int%20*parent%2C%20*rnk%3B%0A%20%20%20%20int%20n%3B%0A%20%0A%20%20%20%20%2F%2F%20Constructor.%0A%20%20%20%20DisjointSets(int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Allocate%20memory%0A%20%20%20%20%20%20%20%20this-%3En%20%3D%20n%3B%0A%20%20%20%20%20%20%20%20parent%20%3D%20new%20int%5Bn%2B1%5D%3B%0A%20%20%20%20%20%20%20%20rnk%20%3D%20new%20int%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initially%2C%20all%20vertices%20are%20in%0A%20%20%20%20%20%20%20%20%2F%2F%20different%20sets%20and%20have%20rank%200.%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20rnk%5Bi%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2Fevery%20element%20is%20parent%20of%20itself%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bi%5D%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Find%20the%20parent%20of%20a%20node%20\u2019u\u2019%0A%20%20%20%20%2F%2F%20Path%20Compression%0A%20%20%20%20int%20find(int%20u)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Make%20the%20parent%20of%20the%20nodes%20in%20the%20path%0A%20%20%20%20%20%20%20%20%20%20%20from%20u\u2013%3E%20parent%5Bu%5D%20point%20to%20parent%5Bu%5D%20*%2F%0A%20%20%20%20%20%20%20%20if%20(u%20!%3D%20parent%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bu%5D%20%3D%20find(parent%5Bu%5D)%3B%0A%20%20%20%20%20%20%20%20return%20parent%5Bu%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Union%20by%20rank%0A%20%20%20%20void%20merge(int%20x%2C%20int%20y)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20x%20%3D%20find(x)%2C%20y%20%3D%20find(y)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Make%20tree%20with%20smaller%20height%0A%20%20%20%20%20%20%20%20%20%20%20a%20subtree%20of%20the%20other%20tree%20%20*%2F%0A%20%20%20%20%20%20%20%20if%20(rnk%5Bx%5D%20%3E%20rnk%5By%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5By%5D%20%3D%20x%3B%0A%20%20%20%20%20%20%20%20else%20%2F%2F%20If%20rnk%5Bx%5D%20%3C%3D%20rnk%5By%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bx%5D%20%3D%20y%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(rnk%5Bx%5D%20%3D%3D%20rnk%5By%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20rnk%5By%5D%2B%2B%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%20%0A%20%2F*%20Functions%20returns%20weight%20of%20the%20MST*%2F%0A%20%0Aint%20Graph%3A%3AkruskalMST()%0A%7B%0A%20%20%20%20int%20mst_wt%20%3D%200%3B%20%2F%2F%20Initialize%20result%0A%20%0A%20%20%20%20%2F%2F%20Sort%20edges%20in%20increasing%20order%20on%20basis%20of%20cost%0A%20%20%20%20sort(edges.begin()%2C%20edges.end())%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20disjoint%20sets%0A%20%20%20%20DisjointSets%20ds(V)%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20all%20sorted%20edges%0A%20%20%20%20vector%3C%20pair%3Cint%2C%20iPair%3E%20%3E%3A%3Aiterator%20it%3B%0A%20%20%20%20for%20(it%3Dedges.begin()%3B%20it!%3Dedges.end()%3B%20it%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20it-%3Esecond.first%3B%0A%20%20%20%20%20%20%20%20int%20v%20%3D%20it-%3Esecond.second%3B%0A%20%0A%20%20%20%20%20%20%20%20int%20set_u%20%3D%20ds.find(u)%3B%0A%20%20%20%20%20%20%20%20int%20set_v%20%3D%20ds.find(v)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20the%20selected%20edge%20is%20creating%0A%20%20%20%20%20%20%20%20%2F%2F%20a%20cycle%20or%20not%20(Cycle%20is%20created%20if%20u%0A%20%20%20%20%20%20%20%20%2F%2F%20and%20v%20belong%20to%20same%20set)%0A%20%20%20%20%20%20%20%20if%20(set_u%20!%3D%20set_v)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Current%20edge%20will%20be%20in%20the%20MST%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20so%20print%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20u%20%3C%3C%20%22%20-%20%22%20%3C%3C%20v%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20MST%20weight%0A%20%20%20%20%20%20%20%20%20%20%20%20mst_wt%20%2B%3D%20it-%3Efirst%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Merge%20two%20sets%0A%20%20%20%20%20%20%20%20%20%20%20%20ds.merge(set_u%2C%20set_v)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20mst_wt%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Let%20us%20create%20above%20shown%20weighted%0A%20%20%20%20%20%20%20and%20unidrected%20graph%20*%2F%0A%20%20%20%20int%20V%20%3D%209%2C%20E%20%3D%2014%3B%0A%20%20%20%20Graph%20g(V%2C%20E)%3B%0A%20%0A%20%20%20%20%2F%2F%20%20making%20above%20shown%20graph%0A%20%20%20%20g.addEdge(0%2C%201%2C%204)%3B%0A%20%20%20%20g.addEdge(0%2C%207%2C%208)%3B%0A%20%20%20%20g.addEdge(1%2C%202%2C%208)%3B%0A%20%20%20%20g.addEdge(1%2C%207%2C%2011)%3B%0A%20%20%20%20g.addEdge(2%2C%203%2C%207)%3B%0A%20%20%20%20g.addEdge(2%2C%208%2C%202)%3B%0A%20%20%20%20g.addEdge(2%2C%205%2C%204)%3B%0A%20%20%20%20g.addEdge(3%2C%204%2C%209)%3B%0A%20%20%20%20g.addEdge(3%2C%205%2C%2014)%3B%0A%20%20%20%20g.addEdge(4%2C%205%2C%2010)%3B%0A%20%20%20%20g.addEdge(5%2C%206%2C%202)%3B%0A%20%20%20%20g.addEdge(6%2C%207%2C%201)%3B%0A%20%20%20%20g.addEdge(6%2C%208%2C%206)%3B%0A%20%20%20%20g.addEdge(7%2C%208%2C%207)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Edges%20of%20MST%20are%20%5Cn%22%3B%0A%20%20%20%20int%20mst_wt%20%3D%20g.kruskalMST()%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnWeight%20of%20MST%20is%20%22%20%3C%3C%20mst_wt%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output :<\/strong><\/p>\n<pre>Edges of MST are \r\n          6 - 7\r\n          2 - 8\r\n          5 - 6\r\n          0 - 1\r\n          2 - 5\r\n          2 - 3\r\n          0 - 7\r\n          3 - 4\r\n          \r\n          Weight of MST is 37<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Kruskal\u2019s Minimum Spanning Tree using STL in C++ &#8211; STL Implementation of Algorithms &#8211; Use a vector of edges which consist of all the edges in the graph.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[81350,81360],"tags":[81743,70802,71248,70796,70799,81745,70769,70783,70784,70774,81746,70794,70781,70772,70789,70785,70801,70771,81744],"class_list":["post-27533","post","type-post","status-publish","format-standard","hentry","category-graph","category-stl-implementation-of-algorithms","tag-c-program-to-implement-minimum-spanning-tree-using-kruskal-algorithm","tag-complexity-of-kruskal-algorithm","tag-difference-between-prims-and-kruskal-algorithm","tag-kruskal","tag-kruskal-algo","tag-kruskal-algorithm-c-adjacency-matrix","tag-kruskal-algorithm-example","tag-kruskal-algorithm-in-c","tag-kruskal-program-in-c","tag-kruskals-algorithm-c","tag-kruskals-algorithm-c-disjoint-set","tag-kruskals-algorithm-example","tag-kruskals-algorithm-in-c","tag-kruskals-algorithm-minimum-spanning-tree","tag-kruskals-algorithm-pdf","tag-prims-algorithm-in-c","tag-prims-and-kruskal-algorithm","tag-time-complexity-of-kruskal-algorithm","tag-write-a-program-for-minimum-spanning-trees-using-kruskals-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27533","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=27533"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27533\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}