{"id":24968,"date":"2017-05-27T18:13:04","date_gmt":"2017-05-27T12:43:04","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=24968"},"modified":"2017-05-27T18:24:30","modified_gmt":"2017-05-27T12:54:30","slug":"kruskals-minimum-spanning-tree-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/kruskals-minimum-spanning-tree-algorithm\/","title":{"rendered":"Kruskal\u2019s Minimum Spanning Tree Algorithm"},"content":{"rendered":"<p>What is Kruskals Minimum Spanning Tree Algorithm?<\/p>\n<p>Given a connected and undirected graph, a <a href=\"https:\/\/www.wikitechy.com\/technology\/amortized-analysis-introduction\/\">spanning tree<\/a> of that graph is a subgraph that is a tree and connects all the vertices together. <span id=\"more-26604\"><\/span>A single graph can have many different spanning trees. A minimum spanning tree (MST) 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<p>How many edges does a minimum spanning tree has?<\/p>\n<p>A minimum spanning tree has (V \u2013 1) edges where V is the number of vertices in the given graph.<\/p>\n<p>What are the applications of Minimum Spanning Tree?<\/p>\n<p>See this for applications of MST.<\/p>\n<p><strong>Below are the steps for finding MST using Kruskal\u2019s algorithm<\/strong><\/p>\n<pre>Sort all the edges in non-decreasing order of their weight.\r\n\r\nPick 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\nRepeat step#2 until there are (V-1) edges in the spanning tree.<\/pre>\n[ad type=\u201dbanner\u201d]\n<p>The step#2 uses Union-Find algorithm to detect cycle. So we recommend to read following post as a prerequisite.<\/p>\n<p>Union-Find Algorithm | Set 1 (Detect Cycle in a Graph)<\/p>\n<p>Union-Find Algorithm | Set 2 (Union By Rank and Path Compression)<\/p>\n<p>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<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-24996\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-8.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"300\" height=\"139\" \/><\/p>\n<p>The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having (9 \u2013 1) = 8 edges.<\/p>\n<pre>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<p>Now pick all edges one by one from sorted list of edges<\/p>\n<p><strong>1.<\/strong> Pick edge 7-6: No cycle is formed, include it.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-24989\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-1.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"264\" height=\"72\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-1.png 264w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-1-260x72.png 260w\" sizes=\"(max-width: 264px) 100vw, 264px\" \/><\/p>\n<p><strong>2.<\/strong> Pick edge 8-2: No cycle is formed, include it.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-24990\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-2.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"264\" height=\"328\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-2.png 264w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-2-241x300.png 241w\" sizes=\"(max-width: 264px) 100vw, 264px\" \/><\/p>\n<p><strong>3. Pick edge 6-5: No cycle is formed, include it.<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-24991\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-3.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"300\" height=\"232\" \/><\/p>\n<p><strong>4.<\/strong> Pick edge 0-1: No cycle is formed, include it.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-24992\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-4.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"300\" height=\"175\" \/><\/p>\n<p><strong>5.<\/strong> Pick edge 2-5: No cycle is formed, include it.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-24993\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-5.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"300\" height=\"175\" \/><\/p>\n<p><strong>6.<\/strong> Pick edge 8-6: Since including this edge results in cycle, discard it.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>7.<\/strong> Pick edge 2-3: No cycle is formed, include it.<\/p>\n<p>\u00a0<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-24994\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-6.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"300\" height=\"175\" \/><\/p>\n<p><strong>8.<\/strong> Pick edge 7-8: Since including this edge results in cycle, discard it.<\/p>\n<p><strong>9.<\/strong> Pick edge 0-7: No cycle is formed, include it.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-24995\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-7.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"300\" height=\"175\" \/><\/p>\n<p><strong>10.<\/strong> Pick edge 1-2: Since including this edge results in cycle, discard it.<\/p>\n<p><strong>11.<\/strong> Pick edge 3-4: No cycle is formed, include it.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-24996\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/kruskals-minimum-spanning-8.png\" alt=\"Kruskal\u2019s Minimum Spanning Tree Algorithm\" width=\"300\" height=\"139\" \/><\/p>\n<p>Since the number of edges included equals (V \u2013 1), the algorithm stops here.<\/p>\n<div id=\"practice\">\n<h4 id=\"recommended\">Recommended:<\/h4>\n<h4 id=\"please-try-your-approach-on-ide-first-before-moving-on-to-the-solution\">Please try your approach on <b><u>{IDE}<\/u><\/b> first, before moving on to the solution.<\/h4>\n<h4 id=\"c\"><strong>C++<\/strong><\/h4>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20for%20Kruskal\u2019s%20algorithm%20to%20find%20Minimum%20Spanning%20Tree%0A%2F%2F%20of%20a%20given%20connected%2C%20undirected%20and%20weighted%20graph%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Cstring.h%3E%0A%20%0A%2F%2F%20a%20structure%20to%20represent%20a%20weighted%20edge%20in%20graph%0Astruct%20Edge%0A%7B%0A%20%20%20%20int%20src%2C%20dest%2C%20weight%3B%0A%7D%3B%0A%20%0A%2F%2F%20a%20structure%20to%20represent%20a%20connected%2C%20undirected%20and%20weighted%20graph%0Astruct%20Graph%0A%7B%0A%20%20%20%20%2F%2F%20V-%3E%20Number%20of%20vertices%2C%20E-%3E%20Number%20of%20edges%0A%20%20%20%20int%20V%2C%20E%3B%0A%20%0A%20%20%20%20%2F%2F%20graph%20is%20represented%20as%20an%20array%20of%20edges.%20Since%20the%20graph%20is%0A%20%20%20%20%2F%2F%20undirected%2C%20the%20edge%20from%20src%20to%20dest%20is%20also%20edge%20from%20dest%0A%20%20%20%20%2F%2F%20to%20src.%20Both%20are%20counted%20as%201%20edge%20here.%0A%20%20%20%20struct%20Edge*%20edge%3B%0A%7D%3B%0A%20%0A%2F%2F%20Creates%20a%20graph%20with%20V%20vertices%20and%20E%20edges%0Astruct%20Graph*%20createGraph(int%20V%2C%20int%20E)%0A%7B%0A%20%20%20%20struct%20Graph*%20graph%20%3D%20(struct%20Graph*)%20malloc(%20sizeof(struct%20Graph)%20)%3B%0A%20%20%20%20graph-%3EV%20%3D%20V%3B%0A%20%20%20%20graph-%3EE%20%3D%20E%3B%0A%20%0A%20%20%20%20graph-%3Eedge%20%3D%20(struct%20Edge*)%20malloc(%20graph-%3EE%20*%20sizeof(%20struct%20Edge%20)%20)%3B%0A%20%0A%20%20%20%20return%20graph%3B%0A%7D%0A%20%0A%2F%2F%20A%20structure%20to%20represent%20a%20subset%20for%20union-find%0Astruct%20subset%0A%7B%0A%20%20%20%20int%20parent%3B%0A%20%20%20%20int%20rank%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20find%20set%20of%20an%20element%20i%0A%2F%2F%20(uses%20path%20compression%20technique)%0Aint%20find(struct%20subset%20subsets%5B%5D%2C%20int%20i)%0A%7B%0A%20%20%20%20%2F%2F%20find%20root%20and%20make%20root%20as%20parent%20of%20i%20(path%20compression)%0A%20%20%20%20if%20(subsets%5Bi%5D.parent%20!%3D%20i)%0A%20%20%20%20%20%20%20%20subsets%5Bi%5D.parent%20%3D%20find(subsets%2C%20subsets%5Bi%5D.parent)%3B%0A%20%0A%20%20%20%20return%20subsets%5Bi%5D.parent%3B%0A%7D%0A%20%0A%2F%2F%20A%20function%20that%20does%20union%20of%20two%20sets%20of%20x%20and%20y%0A%2F%2F%20(uses%20union%20by%20rank)%0Avoid%20Union(struct%20subset%20subsets%5B%5D%2C%20int%20x%2C%20int%20y)%0A%7B%0A%20%20%20%20int%20xroot%20%3D%20find(subsets%2C%20x)%3B%0A%20%20%20%20int%20yroot%20%3D%20find(subsets%2C%20y)%3B%0A%20%0A%20%20%20%20%2F%2F%20Attach%20smaller%20rank%20tree%20under%20root%20of%20high%20rank%20tree%0A%20%20%20%20%2F%2F%20(Union%20by%20Rank)%0A%20%20%20%20if%20(subsets%5Bxroot%5D.rank%20%3C%20subsets%5Byroot%5D.rank)%0A%20%20%20%20%20%20%20%20subsets%5Bxroot%5D.parent%20%3D%20yroot%3B%0A%20%20%20%20else%20if%20(subsets%5Bxroot%5D.rank%20%3E%20subsets%5Byroot%5D.rank)%0A%20%20%20%20%20%20%20%20subsets%5Byroot%5D.parent%20%3D%20xroot%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20ranks%20are%20same%2C%20then%20make%20one%20as%20root%20and%20increment%0A%20%20%20%20%2F%2F%20its%20rank%20by%20one%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20subsets%5Byroot%5D.parent%20%3D%20xroot%3B%0A%20%20%20%20%20%20%20%20subsets%5Bxroot%5D.rank%2B%2B%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Compare%20two%20edges%20according%20to%20their%20weights.%0A%2F%2F%20Used%20in%20qsort()%20for%20sorting%20an%20array%20of%20edges%0Aint%20myComp(const%20void*%20a%2C%20const%20void*%20b)%0A%7B%0A%20%20%20%20struct%20Edge*%20a1%20%3D%20(struct%20Edge*)a%3B%0A%20%20%20%20struct%20Edge*%20b1%20%3D%20(struct%20Edge*)b%3B%0A%20%20%20%20return%20a1-%3Eweight%20%3E%20b1-%3Eweight%3B%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20to%20construct%20MST%20using%20Kruskal\u2019s%20algorithm%0Avoid%20KruskalMST(struct%20Graph*%20graph)%0A%7B%0A%20%20%20%20int%20V%20%3D%20graph-%3EV%3B%0A%20%20%20%20struct%20Edge%20result%5BV%5D%3B%20%20%2F%2F%20Tnis%20will%20store%20the%20resultant%20MST%0A%20%20%20%20int%20e%20%3D%200%3B%20%20%2F%2F%20An%20index%20variable%2C%20used%20for%20result%5B%5D%0A%20%20%20%20int%20i%20%3D%200%3B%20%20%2F%2F%20An%20index%20variable%2C%20used%20for%20sorted%20edges%0A%20%0A%20%20%20%20%2F%2F%20Step%201%3A%20%20Sort%20all%20the%20edges%20in%20non-decreasing%20order%20of%20their%20weight%0A%20%20%20%20%2F%2F%20If%20we%20are%20not%20allowed%20to%20change%20the%20given%20graph%2C%20we%20can%20create%20a%20copy%20of%0A%20%20%20%20%2F%2F%20array%20of%20edges%0A%20%20%20%20qsort(graph-%3Eedge%2C%20graph-%3EE%2C%20sizeof(graph-%3Eedge%5B0%5D)%2C%20myComp)%3B%0A%20%0A%20%20%20%20%2F%2F%20Allocate%20memory%20for%20creating%20V%20ssubsets%0A%20%20%20%20struct%20subset%20*subsets%20%3D%0A%20%20%20%20%20%20%20%20(struct%20subset*)%20malloc(%20V%20*%20sizeof(struct%20subset)%20)%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20V%20subsets%20with%20single%20elements%0A%20%20%20%20for%20(int%20v%20%3D%200%3B%20v%20%3C%20V%3B%20%2B%2Bv)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20subsets%5Bv%5D.parent%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20subsets%5Bv%5D.rank%20%3D%200%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Number%20of%20edges%20to%20be%20taken%20is%20equal%20to%20V-1%0A%20%20%20%20while%20(e%20%3C%20V%20-%201)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%202%3A%20Pick%20the%20smallest%20edge.%20And%20increment%20the%20index%0A%20%20%20%20%20%20%20%20%2F%2F%20for%20next%20iteration%0A%20%20%20%20%20%20%20%20struct%20Edge%20next_edge%20%3D%20graph-%3Eedge%5Bi%2B%2B%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20int%20x%20%3D%20find(subsets%2C%20next_edge.src)%3B%0A%20%20%20%20%20%20%20%20int%20y%20%3D%20find(subsets%2C%20next_edge.dest)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20including%20this%20edge%20does\u2019t%20cause%20cycle%2C%20include%20it%0A%20%20%20%20%20%20%20%20%2F%2F%20in%20result%20and%20increment%20the%20index%20of%20result%20for%20next%20edge%0A%20%20%20%20%20%20%20%20if%20(x%20!%3D%20y)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20result%5Be%2B%2B%5D%20%3D%20next_edge%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20Union(subsets%2C%20x%2C%20y)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%2F%2F%20Else%20discard%20the%20next_edge%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20print%20the%20contents%20of%20result%5B%5D%20to%20display%20the%20built%20MST%0A%20%20%20%20printf(%22Following%20are%20the%20edges%20in%20the%20constructed%20MST%5Cn%22)%3B%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20e%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20\u2013%20%25d%20%3D%3D%20%25d%5Cn%22%2C%20result%5Bi%5D.src%2C%20result%5Bi%5D.dest%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%5Bi%5D.weight)%3B%0A%20%20%20%20return%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%20following%20weighted%20graph%0A%20%20%20%20%20%20%20%20%20%20%20%20%2010%0A%20%20%20%20%20%20%20%200\u2014\u2014\u20131%0A%20%20%20%20%20%20%20%20%7C%20%20%5C%20%20%20%20%20%7C%0A%20%20%20%20%20%20%206%7C%20%20%205%5C%20%20%20%7C15%0A%20%20%20%20%20%20%20%20%7C%20%20%20%20%20%20%5C%20%7C%0A%20%20%20%20%20%20%20%202\u2014\u2014\u20133%0A%20%20%20%20%20%20%20%20%20%20%20%204%20%20%20%20%20%20%20*%2F%0A%20%20%20%20int%20V%20%3D%204%3B%20%20%2F%2F%20Number%20of%20vertices%20in%20graph%0A%20%20%20%20int%20E%20%3D%205%3B%20%20%2F%2F%20Number%20of%20edges%20in%20graph%0A%20%20%20%20struct%20Graph*%20graph%20%3D%20createGraph(V%2C%20E)%3B%0A%20%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%200-1%0A%20%20%20%20graph-%3Eedge%5B0%5D.src%20%3D%200%3B%0A%20%20%20%20graph-%3Eedge%5B0%5D.dest%20%3D%201%3B%0A%20%20%20%20graph-%3Eedge%5B0%5D.weight%20%3D%2010%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%200-2%0A%20%20%20%20graph-%3Eedge%5B1%5D.src%20%3D%200%3B%0A%20%20%20%20graph-%3Eedge%5B1%5D.dest%20%3D%202%3B%0A%20%20%20%20graph-%3Eedge%5B1%5D.weight%20%3D%206%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%200-3%0A%20%20%20%20graph-%3Eedge%5B2%5D.src%20%3D%200%3B%0A%20%20%20%20graph-%3Eedge%5B2%5D.dest%20%3D%203%3B%0A%20%20%20%20graph-%3Eedge%5B2%5D.weight%20%3D%205%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%201-3%0A%20%20%20%20graph-%3Eedge%5B3%5D.src%20%3D%201%3B%0A%20%20%20%20graph-%3Eedge%5B3%5D.dest%20%3D%203%3B%0A%20%20%20%20graph-%3Eedge%5B3%5D.weight%20%3D%2015%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%202-3%0A%20%20%20%20graph-%3Eedge%5B4%5D.src%20%3D%202%3B%0A%20%20%20%20graph-%3Eedge%5B4%5D.dest%20%3D%203%3B%0A%20%20%20%20graph-%3Eedge%5B4%5D.weight%20%3D%204%3B%0A%20%0A%20%20%20%20KruskalMST(graph)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"ad-typebanner\">[ad type=\u201dbanner\u201d]<\/h4>\n<h4 id=\"java\"><strong>JAVA<\/strong><\/h4>\n<\/div>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20for%20Kruskal\u2019s%20algorithm%20to%20find%20Minimum%20Spanning%20Tree%0A%2F%2F%20of%20a%20given%20connected%2C%20undirected%20and%20weighted%20graph%0Aimport%20java.util.*%3B%0Aimport%20java.lang.*%3B%0Aimport%20java.io.*%3B%0A%20%0Aclass%20Graph%0A%7B%0A%20%20%20%20%2F%2F%20A%20class%20to%20represent%20a%20graph%20edge%0A%20%20%20%20class%20Edge%20implements%20Comparable%3CEdge%3E%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20src%2C%20dest%2C%20weight%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Comparator%20function%20used%20for%20sorting%20edges%20based%20on%0A%20%20%20%20%20%20%20%20%2F%2F%20their%20weight%0A%20%20%20%20%20%20%20%20public%20int%20compareTo(Edge%20compareEdge)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20this.weight-compareEdge.weight%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20A%20class%20to%20represent%20a%20subset%20for%20union-find%0A%20%20%20%20class%20subset%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20parent%2C%20rank%3B%0A%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20int%20V%2C%20E%3B%20%20%20%20%2F%2F%20V-%3E%20no.%20of%20vertices%20%26%20E-%3Eno.of%20edges%0A%20%20%20%20Edge%20edge%5B%5D%3B%20%2F%2F%20collection%20of%20all%20edges%0A%20%0A%20%20%20%20%2F%2F%20Creates%20a%20graph%20with%20V%20vertices%20and%20E%20edges%0A%20%20%20%20Graph(int%20v%2C%20int%20e)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20V%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20E%20%3D%20e%3B%0A%20%20%20%20%20%20%20%20edge%20%3D%20new%20Edge%5BE%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Ce%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20edge%5Bi%5D%20%3D%20new%20Edge()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20utility%20function%20to%20find%20set%20of%20an%20element%20i%0A%20%20%20%20%2F%2F%20(uses%20path%20compression%20technique)%0A%20%20%20%20int%20find(subset%20subsets%5B%5D%2C%20int%20i)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20find%20root%20and%20make%20root%20as%20parent%20of%20i%20(path%20compression)%0A%20%20%20%20%20%20%20%20if%20(subsets%5Bi%5D.parent%20!%3D%20i)%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Bi%5D.parent%20%3D%20find(subsets%2C%20subsets%5Bi%5D.parent)%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20subsets%5Bi%5D.parent%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20function%20that%20does%20union%20of%20two%20sets%20of%20x%20and%20y%0A%20%20%20%20%2F%2F%20(uses%20union%20by%20rank)%0A%20%20%20%20void%20Union(subset%20subsets%5B%5D%2C%20int%20x%2C%20int%20y)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20xroot%20%3D%20find(subsets%2C%20x)%3B%0A%20%20%20%20%20%20%20%20int%20yroot%20%3D%20find(subsets%2C%20y)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Attach%20smaller%20rank%20tree%20under%20root%20of%20high%20rank%20tree%0A%20%20%20%20%20%20%20%20%2F%2F%20(Union%20by%20Rank)%0A%20%20%20%20%20%20%20%20if%20(subsets%5Bxroot%5D.rank%20%3C%20subsets%5Byroot%5D.rank)%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Bxroot%5D.parent%20%3D%20yroot%3B%0A%20%20%20%20%20%20%20%20else%20if%20(subsets%5Bxroot%5D.rank%20%3E%20subsets%5Byroot%5D.rank)%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Byroot%5D.parent%20%3D%20xroot%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20ranks%20are%20same%2C%20then%20make%20one%20as%20root%20and%20increment%0A%20%20%20%20%20%20%20%20%2F%2F%20its%20rank%20by%20one%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Byroot%5D.parent%20%3D%20xroot%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Bxroot%5D.rank%2B%2B%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%20The%20main%20function%20to%20construct%20MST%20using%20Kruskal\u2019s%20algorithm%0A%20%20%20%20void%20KruskalMST()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Edge%20result%5B%5D%20%3D%20new%20Edge%5BV%5D%3B%20%20%2F%2F%20Tnis%20will%20store%20the%20resultant%20MST%0A%20%20%20%20%20%20%20%20int%20e%20%3D%200%3B%20%20%2F%2F%20An%20index%20variable%2C%20used%20for%20result%5B%5D%0A%20%20%20%20%20%20%20%20int%20i%20%3D%200%3B%20%20%2F%2F%20An%20index%20variable%2C%20used%20for%20sorted%20edges%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3CV%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20result%5Bi%5D%20%3D%20new%20Edge()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%201%3A%20%20Sort%20all%20the%20edges%20in%20non-decreasing%20order%20of%20their%0A%20%20%20%20%20%20%20%20%2F%2F%20weight.%20%20If%20we%20are%20not%20allowed%20to%20change%20the%20given%20graph%2C%20we%0A%20%20%20%20%20%20%20%20%2F%2F%20can%20create%20a%20copy%20of%20array%20of%20edges%0A%20%20%20%20%20%20%20%20Arrays.sort(edge)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Allocate%20memory%20for%20creating%20V%20ssubsets%0A%20%20%20%20%20%20%20%20subset%20subsets%5B%5D%20%3D%20new%20subset%5BV%5D%3B%0A%20%20%20%20%20%20%20%20for(i%3D0%3B%20i%3CV%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Bi%5D%3Dnew%20subset()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20V%20subsets%20with%20single%20elements%0A%20%20%20%20%20%20%20%20for%20(int%20v%20%3D%200%3B%20v%20%3C%20V%3B%20%2B%2Bv)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Bv%5D.parent%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20subsets%5Bv%5D.rank%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20i%20%3D%200%3B%20%20%2F%2F%20Index%20used%20to%20pick%20next%20edge%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Number%20of%20edges%20to%20be%20taken%20is%20equal%20to%20V-1%0A%20%20%20%20%20%20%20%20while%20(e%20%3C%20V%20-%201)%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%20Step%202%3A%20Pick%20the%20smallest%20edge.%20And%20increment%20the%20index%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20for%20next%20iteration%0A%20%20%20%20%20%20%20%20%20%20%20%20Edge%20next_edge%20%3D%20new%20Edge()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next_edge%20%3D%20edge%5Bi%2B%2B%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20x%20%3D%20find(subsets%2C%20next_edge.src)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20y%20%3D%20find(subsets%2C%20next_edge.dest)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20including%20this%20edge%20does\u2019t%20cause%20cycle%2C%20include%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20in%20result%20and%20increment%20the%20index%20of%20result%20for%20next%20edge%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(x%20!%3D%20y)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%5Be%2B%2B%5D%20%3D%20next_edge%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Union(subsets%2C%20x%2C%20y)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Else%20discard%20the%20next_edge%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20print%20the%20contents%20of%20result%5B%5D%20to%20display%20the%20built%20MST%0A%20%20%20%20%20%20%20%20System.out.println(%22Following%20are%20the%20edges%20in%20the%20constructed%20MST%22)%3B%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20e%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(result%5Bi%5D.src%2B%22%20\u2013%20%22%2Bresult%5Bi%5D.dest%2B%22%20%3D%3D%20%22%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%5Bi%5D.weight)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20Program%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20following%20weighted%20graph%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2010%0A%20%20%20%20%20%20%20%20%20%20%20%200\u2014\u2014\u20131%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%5C%20%20%20%20%20%7C%0A%20%20%20%20%20%20%20%20%20%20%206%7C%20%20%205%5C%20%20%20%7C15%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%20%20%20%20%5C%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%202\u2014\u2014\u20133%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%204%20%20%20%20%20%20%20*%2F%0A%20%20%20%20%20%20%20%20int%20V%20%3D%204%3B%20%20%2F%2F%20Number%20of%20vertices%20in%20graph%0A%20%20%20%20%20%20%20%20int%20E%20%3D%205%3B%20%20%2F%2F%20Number%20of%20edges%20in%20graph%0A%20%20%20%20%20%20%20%20Graph%20graph%20%3D%20new%20Graph(V%2C%20E)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%200-1%0A%20%20%20%20%20%20%20%20graph.edge%5B0%5D.src%20%3D%200%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B0%5D.dest%20%3D%201%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B0%5D.weight%20%3D%2010%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%200-2%0A%20%20%20%20%20%20%20%20graph.edge%5B1%5D.src%20%3D%200%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B1%5D.dest%20%3D%202%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B1%5D.weight%20%3D%206%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%200-3%0A%20%20%20%20%20%20%20%20graph.edge%5B2%5D.src%20%3D%200%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B2%5D.dest%20%3D%203%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B2%5D.weight%20%3D%205%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%201-3%0A%20%20%20%20%20%20%20%20graph.edge%5B3%5D.src%20%3D%201%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B3%5D.dest%20%3D%203%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B3%5D.weight%20%3D%2015%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%202-3%0A%20%20%20%20%20%20%20%20graph.edge%5B4%5D.src%20%3D%202%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B4%5D.dest%20%3D%203%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B4%5D.weight%20%3D%204%3B%0A%20%0A%20%20%20%20%20%20%20%20graph.KruskalMST()%3B%0A%20%20%20%20%7D%0A%7D%0A%2F%2FThis%20code%20is%20contributed%20by%20Aakash%20Hasija%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"python\"><strong>Python<\/strong><\/h4>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20for%20Kruskal\u2019s%20algorithm%20to%20find%20Minimum%20Spanning%20Tree%0A%23%20of%20a%20given%20connected%2C%20undirected%20and%20weighted%20graph%0A%20%0Afrom%20collections%20import%20defaultdict%0A%20%0A%23Class%20to%20represent%20a%20graph%0Aclass%20Graph%3A%0A%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20%5B%5D%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv%2Cw)%3A%0A%20%20%20%20%20%20%20%20self.graph.append(%5Bu%2Cv%2Cw%5D)%0A%20%0A%20%20%20%20%23%20A%20utility%20function%20to%20find%20set%20of%20an%20element%20i%0A%20%20%20%20%23%20(uses%20path%20compression%20technique)%0A%20%20%20%20def%20find(self%2C%20parent%2C%20i)%3A%0A%20%20%20%20%20%20%20%20if%20parent%5Bi%5D%20%3D%3D%20i%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20i%0A%20%20%20%20%20%20%20%20return%20self.find(parent%2C%20parent%5Bi%5D)%0A%20%0A%20%20%20%20%23%20A%20function%20that%20does%20union%20of%20two%20sets%20of%20x%20and%20y%0A%20%20%20%20%23%20(uses%20union%20by%20rank)%0A%20%20%20%20def%20union(self%2C%20parent%2C%20rank%2C%20x%2C%20y)%3A%0A%20%20%20%20%20%20%20%20xroot%20%3D%20self.find(parent%2C%20x)%0A%20%20%20%20%20%20%20%20yroot%20%3D%20self.find(parent%2C%20y)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Attach%20smaller%20rank%20tree%20under%20root%20of%20high%20rank%20tree%0A%20%20%20%20%20%20%20%20%23%20(Union%20by%20Rank)%0A%20%20%20%20%20%20%20%20if%20rank%5Bxroot%5D%20%3C%20rank%5Byroot%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bxroot%5D%20%3D%20yroot%0A%20%20%20%20%20%20%20%20elif%20rank%5Bxroot%5D%20%3E%20rank%5Byroot%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Byroot%5D%20%3D%20xroot%0A%20%20%20%20%20%20%20%20%23If%20ranks%20are%20same%2C%20then%20make%20one%20as%20root%20and%20increment%0A%20%20%20%20%20%20%20%20%23%20its%20rank%20by%20one%0A%20%20%20%20%20%20%20%20else%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Byroot%5D%20%3D%20xroot%0A%20%20%20%20%20%20%20%20%20%20%20%20rank%5Bxroot%5D%20%2B%3D%201%0A%20%0A%20%20%20%20%23%20The%20main%20function%20to%20construct%20MST%20using%20Kruskal\u2019s%20algorithm%0A%20%20%20%20def%20KruskalMST(self)%3A%0A%20%0A%20%20%20%20%20%20%20%20result%20%3D%5B%5D%20%23This%20will%20store%20the%20resultant%20MST%0A%20%0A%20%20%20%20%20%20%20%20i%20%3D%200%20%23%20An%20index%20variable%2C%20used%20for%20sorted%20edges%0A%20%20%20%20%20%20%20%20e%20%3D%200%20%23%20An%20index%20variable%2C%20used%20for%20result%5B%5D%0A%20%0A%20%20%20%20%20%20%20%20%23Step%201%3A%20%20Sort%20all%20the%20edges%20in%20non-decreasing%20order%20of%20their%0A%20%20%20%20%20%20%20%20%23%20weight.%20%20If%20we%20are%20not%20allowed%20to%20change%20the%20given%20graph%2C%20we%0A%20%20%20%20%20%20%20%20%23%20can%20create%20a%20copy%20of%20graph%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20%20sorted(self.graph%2Ckey%3Dlambda%20item%3A%20item%5B2%5D)%0A%20%20%20%20%20%20%20%20%23print%20self.graph%0A%20%0A%20%20%20%20%20%20%20%20parent%20%3D%20%5B%5D%20%3B%20rank%20%3D%20%5B%5D%0A%20%0A%20%20%20%20%20%20%20%20%23%20Create%20V%20subsets%20with%20single%20elements%0A%20%20%20%20%20%20%20%20for%20node%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent.append(node)%0A%20%20%20%20%20%20%20%20%20%20%20%20rank.append(0)%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Number%20of%20edges%20to%20be%20taken%20is%20equal%20to%20V-1%0A%20%20%20%20%20%20%20%20while%20e%20%3C%20self.V%20-1%20%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Step%202%3A%20Pick%20the%20smallest%20edge%20and%20increment%20the%20index%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20for%20next%20iteration%0A%20%20%20%20%20%20%20%20%20%20%20%20u%2Cv%2Cw%20%3D%20%20self.graph%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20i%20%2B%201%0A%20%20%20%20%20%20%20%20%20%20%20%20x%20%3D%20self.find(parent%2C%20u)%0A%20%20%20%20%20%20%20%20%20%20%20%20y%20%3D%20self.find(parent%20%2Cv)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20including%20this%20edge%20does\u2019t%20cause%20cycle%2C%20include%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20in%20result%20and%20increment%20the%20index%20of%20result%20for%20next%20edge%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20x%20!%3D%20y%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20e%20%3D%20e%20%2B%201%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result.append(%5Bu%2Cv%2Cw%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.union(parent%2C%20rank%2C%20x%2C%20y)%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Else%20discard%20the%20edge%0A%20%0A%20%20%20%20%20%20%20%20%23%20print%20the%20contents%20of%20result%5B%5D%20to%20display%20the%20built%20MST%0A%20%20%20%20%20%20%20%20print%20%22Following%20are%20the%20edges%20in%20the%20constructed%20MST%22%0A%20%20%20%20%20%20%20%20for%20u%2Cv%2Cweight%20%20in%20result%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23print%20str(u)%20%2B%20%22%20\u2013%20%22%20%2B%20str(v)%20%2B%20%22%20%3D%3D%20%22%20%2B%20str(weight)%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20(%22%25d%20\u2013%20%25d%20%3D%3D%20%25d%22%20%25%20(u%2Cv%2Cweight))%0A%20%0A%20%0Ag%20%3D%20Graph(4)%0Ag.addEdge(0%2C%201%2C%2010)%0Ag.addEdge(0%2C%202%2C%206)%0Ag.addEdge(0%2C%203%2C%205)%0Ag.addEdge(1%2C%203%2C%2015)%0Ag.addEdge(2%2C%203%2C%204)%0A%20%0Ag.KruskalMST()%0A%20%0A%23This%20code%20is%20contributed%20by%20Neelam%20Yadav\u201d message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<pre>Following are the edges in the constructed MST\r\n2 -- 3 == 4\r\n0 -- 3 == 5\r\n0 -- 1 == 10<\/pre>\n<p><strong>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(V<sup>2<\/sup>), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Kruskal\u2019s Minimum Spanning Tree Algorithm-Greedy Algorithm-Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees<\/p>\n","protected":false},"author":1,"featured_media":25352,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70144],"tags":[70802,70807,70598,70796,70799,70764,70769,70783,70784,70754,70774,70794,70781,70772,70806,70805,70767,70793,70795,70779,70766,70792,70763,70770,70775,70785,70804,70778,70776,70801,70777,70786,70773,70046,70765,70791,70797,70798,70771,70803,70788,70782],"class_list":["post-24968","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-greedy-algorithm","tag-complexity-of-kruskal-algorithm","tag-complexity-of-prims-algorithm","tag-graph-algorithms","tag-kruskal","tag-kruskal-algo","tag-kruskal-algorithm","tag-kruskal-algorithm-example","tag-kruskal-algorithm-in-c","tag-kruskal-program-in-c","tag-kruskals-algorithm","tag-kruskals-algorithm-c","tag-kruskals-algorithm-example","tag-kruskals-algorithm-in-c","tag-kruskals-algorithm-minimum-spanning-tree","tag-maximum-spanning-tree","tag-minimum-cost-spanning-tree","tag-minimum-spanning-tree","tag-minimum-spanning-tree-algorithm","tag-minimum-spanning-tree-example","tag-minimum-spanning-tree-prims-algorithm","tag-prim","tag-prim-algorithm","tag-prims-algorithm","tag-prims-algorithm-example","tag-prims-algorithm-for-minimum-spanning-tree","tag-prims-algorithm-in-c","tag-prims-algorithm-minimum-spanning-tree","tag-prims-algorithm-pseudocode","tag-prims-algorithm-with-example","tag-prims-and-kruskal-algorithm","tag-prims-and-kruskal-algorithm-with-example","tag-prims-program-in-c","tag-prism-algorithm","tag-quicksort","tag-spanning-tree","tag-spanning-tree-algorithm","tag-spanning-tree-example","tag-spanning-tree-in-data-structure","tag-time-complexity-of-kruskal-algorithm","tag-tree-algorithms","tag-what-is-span","tag-what-is-spanning-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24968","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=24968"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24968\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/25352"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=24968"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=24968"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=24968"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}