Last Updated: 9 Jan, 2021

# Kruskal’s Minimum Spanning Tree Algorithm

Moderate

## Problem statement

#### 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

### 01 Approach

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:

1. Create variable ‘cost’ and initialize it to zero, which stores the weight of the minimum spanning tree.
2. Sort the array/list of edges in ascending order of their weight.
3. 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.
4. Finally, return ‘cost’.