Kruskal’s Algorithm — A Summary

I’d like to talk about one of the greedy algorithms used in obtaining a minimum spanning tree — Kruskal’s.

But before we begin discussing the algorithm lets talk about what is a minimum spanning tree and why do we need them.

Minimum Spanning Tree

A spanning tree of a graph is a tree that connects every vertex of the graph and is a subgraph of the graph. The cost of a spanning tree is sum of all the edge’s weight. Minimum spanning tree (MST) is therefore a least cost spanning tree.

Need for MST

MST have a multitude of application in real life scenarios which involve reducing or achieving the minimum cost.

1. Designing LAN’s

2. Supplying houses with electricity, water, telephone and internet lines.

3. Constructing Highways or railway tracks across multiple cities.

Kruskal Algorithm

Kruskal’s Algorithm works on an undirected graph to find it’s minimum spanning tree. A tree is basically a graph with no cycles formed.

Kruskal’s algorithm is an algorithm as with each step it selects the lowest weighted edge to add which also does not complete a circle with the edges selected already.

Kruskal’s is an improved version of a greedy algorithm and the greedy choice is to choose the least weighted edge that does not generate a cycle in the MST that has been constructed thus far.

Graphical Representation

Let’s have a look at how Kruskal’s method works using an example. An example will help you grasp Kruskal’s algorithm.

Assume a weighted graph is -

Step 1: Start with the smallest edge which would be B-D.

Step 2: Continue with the next lowest weight which is the edges B-C and D-E.

Step 3: Connect E-G and C-F.

Step 4: For weight 4, we have two edges A-C and C-D. We connect A-C but not C-D because it would create a cycle in the tree and those two vertices are already connected.

Step 5: There are n-1 edges in the graph and this will be the output of Kruskal’s algorithm.

Pseudocode and working

KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
    MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
    if FIND-SET(u) ≠ FIND-SET(v):       
    A = A ∪ {(u, v)}
    UNION(u, v)
return A

The algorithm works as follows:

1. Sort all the edges from low weight to high weight.
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge. We check this condition by checking if the vertices are already part of the tree.
3. Keep adding edges until we cover all the vertices.

I hope this blog provides sufficient information about Greedy approach and Kruskal’s Algorithm.