Last Updated: 9 Jan, 2021
Kruskal’s Minimum Spanning Tree Algorithm
Moderate
Asked in companies
A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices without any cycles and with the minimum possible total edge weight.
A spanning tree’s weight is the sum of the weights of each edge in the spanning tree.
You have been given a connected undirected weighted graph having 'n' vertices, from 1 to 'n', and 'm' edges.
You are given an array 'edges' of size 'm', containing the details of the edges of the graph.
Each element of 'edges' contains three integers, the two vertices that are being connected and the weight of the edge.
Find the weight of the minimum spanning tree of the given graph.
Example :
Input: 'n' = 5, 'm' = 6
'edges' = [[1, 2, 6], [2, 3, 5], [3, 4, 4], [1, 4, 1], [1, 3, 2], [3, 5, 3]]
Output: 11
Explanation: The given graph is:
The minimum spanning tree of the graph is:
And its weight is 1 + 2 + 5 + 3 = 11.
Input Format:
The first line contains two integers, 'n' and 'm' denoting the number of vertices and edges in the graph, respectively.
The next 'm' lines contain three space integers, the vertices 'u' and 'v', and the weight 'w'.
Output Format:
Print the weight of the minimum spanning tree of the given graph.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Approaches
The basic idea of Kruskal’s algorithm is to sort the edges of the graph in non-decreasing order by its weight. And place all the original graph nodes isolated from each other to form a forest of single-node trees. Then, at each algorithm step, we will try to merge the trees by an edge of the original graph. The idea here is to choose the edges greedily. At each iteration, choose the edge with the minimum weight not previously chosen.
While choosing the edge, we will ensure it doesn’t belong to the same subtrees (because adding that edge will create a cycle).
The basic idea of this approach is to use a Disjoint Set Union data structure to solve this task. You can refer to this article from cp-algorithms to read more about DSU. https://cp-algorithms.com/data_structures/disjoint_set_union.html
DSU will help us to check whether two vertices are in the same subtree or not and also to merge two subtrees efficiently.
The steps are as follows:
- Create variable ‘cost’ and initialize it to zero, which stores the weight of the minimum spanning tree.
- Sort the array/list of edges in ascending order of their weight.
- Now start iterating the array/list of edges.
- Check whether both vertices of the current edge ('u', 'v') belong to different subtrees. If they are not, then:
- Add the weight of the current edge to ‘cost’.
- Merge the two subtrees.
- Check whether both vertices of the current edge ('u', 'v') belong to different subtrees. If they are not, then:
- Finally, return ‘cost’.
Have to Delete