Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 9 Jan, 2021

Moderate

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

```
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'.
```

```
Print the weight of the minimum spanning tree of the given graph.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

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

Similar problems

Minimum Swaps To Make Identical Array

Moderate

Posted: 22 Jan, 2022

Find Center of Star Graph

Easy

Posted: 26 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022