Kruskal’s algorithm for finding MST

Kruskal’s algorithm for finding MST(Minimum Spanning Tree)

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach.

To understand Kruskal's algorithm let us consider the following example –

Step 1 - Remove all loops and Parallel Edges

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Arrange all edges in their increasing order of weight

Step 3 - Add the edge which has the least weightage

Now we start adding edges to the graph beginning from the one which has the least weight. Throughout, we shall keep checking that the spanning properties remain intact. In case, by adding one edge, the spanning tree property does not hold (forms a cycle) then we shall not include the edge in the graph.

The least cost is 2 and edges involved are B,D and D,T. We add them.

Next cost is 3, and associated edges are A,C and C,D. We add them again –

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph. We ignore it.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move on.

Now we are left with only one node to be added. Between the two least cost edges available 7 and 8, we shall add the edge with cost 7.

By adding edge S,A we have included all the nodes of the graph and we now have minimum cost spanning tree.

Example 2: