Kruskal's Algorithm - Step by Step

March 10, 2019

Kruskal’s algorithm is an algorithm for finding minimum spanning trees - how to connect all nodes in a graph while keeping the sum of edge weights the smallest.

A Step-by-Step Walkthrough

Take a look at this graph!

Graph 0
Graph 0

In every iteration of our algorithm, we select the edges with the smallest weights that don’t create a cycle. So in the first iteration, our selection goes like this:

Graph 1
Graph 1

The next step needs a little more thought. We have 3 edges here that all have a weight of 2 - AFAF, CECE and CDCD. We can arbitrarily choose one of them in this case, so for example, I choose CECE.

Graph 2
Graph 2

Now, among all the remaining edges, 2 is still the smallest weight. However, CDCD will create a cycle for us, so we should add this edge to our black list and continue - add AFAF to our selection.

Graph 3
Graph 3

With all the edges of weight 2 being dealt with, the next step is pretty straightforward.

Graph 4
Graph 4

Then finally selecting BDBD to connect all nodes inside a same tree.

Graph 5
Graph 5

And that’s it! We have found our minimum spanning tree with Kruskal’s algorithm!

Graph 6
Graph 6

Pseudo Code

Procedure kruskal(E, T : Sequence of Edge, P : UnionFind)
  sort E by increasing edge weight
  foreach {u, v} ∈ E do
    if u and v are in different components of P then
      add edge {u, v} to T
      join the partitions of u and v in P

The time complexity of this algorithm is O((n+m)log m)O((n+m)\cdot log\ m).