What is Kruskal’s algorithm?

Kruskal’s algorithm

Kruskal’s algorithm is a minimum spanning tree algorithm. The algorithm finds an edge of the least weight that connects any two trees in the forest. It is a greedy algorithm in the graph that finds a minimum spanning tree for a connected weighted graph and adds increasing weightage at each step.

Applications

1. It is applied to layout electrical wiring.

2. It is used in computer network (LAN connection)

Step by step

Step 1

First, we have to remove all loops and parallel edges to the graph.

In the case of parallel edges, we have to first keep the one with the least weightage associated and remove all others.

Step 2

In the next step, we have to arrange all sets of edges and weights in ascending order.

Step 3

We should start adding edges to the graph, beginning from the one with the least weightage. Throughout, we shall keep checking that we don’t disturb the spanning properties. If adding one edge to the spanning tree property does not hold, we will consider not including the edge in the graph.

So the least weight from the graph is 2, and the edges involved are B, D, and D, T. We will add them, which does not violate the spanning-tree properties, and continue on with our next selection.

After 2, the next smallest weight is 3 with the involved edges of A, C, and C, D. We will add them again.

After 3, the next smallest weight in the table is 4. We can observe that adding it will form a self-loop in the graph.

We ignore it. In this process, we shall ignore all edges that form a self-loop.

We observe that edges with weights of 5 and 6 also form a self-loop. We avoid them and move on with the next step.

Now, we are only left with one node to be added. We will add this node between the two edges, with the smallest weight available (7 and 8), and add the edge with a weightage 7.

By adding edge S, A, we have included all the graph nodes. Now, we have a minimum cost spanning tree using Kruskal’s algorithm.