Minimum Spanning Tree

Kruskal Algorithm

Problem Statement

Kruskal Algorithm starts with all nodes separated from each other i.e., they don't have edge between them. To find MST from graph, sort edges of graph in a non-decreasing manner.

Next, connect edges from left to right. If current picked edge is already connected in tree, then continue the process. Else, connect those two nodes with dsu (disjoint set union).

Approach

1. Sort graph edges with respect to their weights in a non-decreasing manner.

2. Transverse left-to-right i..e, from smaller to larger weights and add edges to MST.

3. Add edges that don't form cycles, edges connecting only disconnected components.

How to determine whether two vertices are connected?

Dfs approach can be used to check if two vertices are connected. First, start dfs from any vertex, and then check whether 2nd vertex has been visited. It can be run efficiently by DSU.

How to implement the solution in different languages?