Kruskal Algorithm

DEFINITION - Minimum Cost Spanning Tree

Let G=(V,E,W) be any weighted graph. Then a spanning tree whose cost is minimum is called minimum spanning tree. The cost of the spanning tree is defined as the sum of the costs of the edges in that tree.

Kruskal’s Algorithm

Kruskal’s Algorithm uses greedy approach to select an edge with a minimum cost that doesn't result in cycle when added to already selected edges. Time complexity of Kruskal’s algorithm is o(n+eloge).
In this method all the edges are arranged in the increasing order of the cost. Now select one by one the edges with minimum cost but edges are accepted if and only if there is no cycle. All the other edges having high cost or cycle is formed are rejected.

The steps involved are

Step 1: Construct a min heap of edges on the basis of ascending order of cost of edges.

Step 2: Delete edge from heap and add to minimum cost spanning tree T if no cycle

Step 3: Repeat until e=n-1 or heap is empty

EXAMPLE