Minimum Spanning Tree - Kruskal's Algorithm

Kruskal’s Algorithm

Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal’s Algorithm follows the Greedy approach as in each iteration it finds an edge that has the least weight and adds it to the growing spanning tree.

Solution

The algorithm follows the steps listed below:

• Sort the graph edges with respect to their weights.
• Start adding edges to the minimum spanning tree from the edge with the smallest weight until the edge of the largest weight.
• Only add edges that don’t form a cycle (edges that connect only disconnected components).

So now the question is how to check if 2 vertices are connected or not?

This could be done using Depth-First Search which starts from the first vertex and then checks if the second vertex is visited or not. But Depth-First Search will make the time complexity large as it has an order of ...