Greedy Algorithms | Set 2 (Kruskal’s Minimum Spanning Tree Algorithm)

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

[ad type=”banner”]

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

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

2. 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.  

3. Repeat step#2 until there are (V-1) edges in the spanning tree.

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.

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

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

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

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

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

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

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

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

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.

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.

 

Python programming:

[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()” message=”” 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(V²), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)

[ad type=”banner”]