Kruskal's Algorithm

In this lesson, we’ll study Kruskal’s algorithm, which makes use of a surprisingly straightforward strategy to assemble a minimum spanning tree.

Computing MSTs with Kruskal’s algorithm

The input to Kruskal’s algorithm is a connected, weighted, undirected graph $G = (V, E, w)$. The algorithm iteratively builds up an acyclic graph $T = (V, F, w)$ with $F \subseteq E$. In the beginning, $F$ is empty. The edges will be added until $T$ is a spanning tree of $G$.

First, we’ll sort all edges of $E$ by their weight $w(e)$ in increasing order. Next, we’ll inspect each edge $e = (u, v)$ in this order, one by one. If $u$ and $v$ are in different connected components of $T$, we’ll add $e$ to $F$. Otherwise, we’ll skip $e$, as it would introduce a cycle in $T$.

We’ll continue this strategy until we have processed all edges, at which point $T$ is a spanning tree of $G$.

Let’s illustrate the algorithm on the example graph from the previous lesson:

The edge with the lowest weight is $(a, c)$ with weight $2$. We’ll add it as the first edge to our subgraph $T$ (marked in blue below).

The next edges are $(b, d)$ of weight $3$ and ...