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 ${O(V+E)}$ where V is the number of vertices and E is the number of edges.

The best solution is Disjoint sets.

Disjoint sets are sets whose intersection is the empty set. It means that they don’t have any element in common.

In Kruskal’s Algorithm, at each iteration, we will select the edge with the lowest weight. So, we will start with the lowest weighted edge first.

Kruskal’s Algorithm is a greedy algorithm, because at each step it adds to the forest an edge of least possible weight.

Let us visualize how Kruskal’s Algorithm works.