What is Kruskals Minimum Spanning Tree 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. 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.

How many edges does a minimum spanning tree has?

A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.

What are the applications of Minimum Spanning Tree?

See this for applications of MST.

Below are the steps for finding MST using Kruskal’s algorithm

Sort all the edges in non-decreasing order of their weight.

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.  

Repeat step#2 until there are (V-1) edges in the spanning tree.
[ad type=”banner”]

The step#2 uses Union-Find algorithm to detect cycle. So we recommend to read following post as a prerequisite.

Union-Find Algorithm | Set 1 (Detect Cycle in a Graph)

Union-Find Algorithm | Set 2 (Union By Rank and Path Compression)

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.

Kruskal’s Minimum Spanning Tree Algorithm

The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having (9 – 1) = 8 edges.

After sorting:
Weight   Src    Dest
1         7      6
2         8      2
2         6      5
4         0      1
4         2      5
6         8      6
7         2      3
7         7      8
8         0      7
8         1      2
9         3      4
10        5      4
11        1      7
14        3      5

Now pick all edges one by one from sorted list of edges

1. Pick edge 7-6: No cycle is formed, include it.

Kruskal’s Minimum Spanning Tree Algorithm

2. Pick edge 8-2: No cycle is formed, include it.

Kruskal’s Minimum Spanning Tree Algorithm

3. Pick edge 6-5: No cycle is formed, include it.

Kruskal’s Minimum Spanning Tree Algorithm

4. Pick edge 0-1: No cycle is formed, include it.

Kruskal’s Minimum Spanning Tree Algorithm

5. Pick edge 2-5: No cycle is formed, include it.

Kruskal’s Minimum Spanning Tree Algorithm

6. Pick edge 8-6: Since including this edge results in cycle, discard it.

[ad type=”banner”]

7. Pick edge 2-3: No cycle is formed, include it.

 

Kruskal’s Minimum Spanning Tree Algorithm

8. Pick edge 7-8: Since including this edge results in cycle, discard it.

9. Pick edge 0-7: No cycle is formed, include it.

Kruskal’s Minimum Spanning Tree Algorithm

10. Pick edge 1-2: Since including this edge results in cycle, discard it.

11. Pick edge 3-4: No cycle is formed, include it.

Kruskal’s Minimum Spanning Tree Algorithm

Since the number of edges included equals (V – 1), the algorithm stops here.

Recommended:

Please try your approach on {IDE} first, before moving on to the solution.

C++

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20for%20Kruskal’s%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’s%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’t%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–%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——–1%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——–3%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” message=”” highlight=”” provider=”manual”/]

[ad type=”banner”]

JAVA

[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20for%20Kruskal’s%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’s%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’t%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–%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——–1%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——–3%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” message=”” highlight=”” provider=”manual”/]

Python

[pastacode lang=”python” manual=”%23%20Python%20program%20for%20Kruskal’s%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’s%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’t%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–%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–%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” message=”Python” highlight=”” provider=”manual”/]
Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Time Complexity: 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), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)

Categorized in: