Kruskal’s Algorithm

Introduction to Kruskal’s algorithm

The last minimum spanning tree algorithm we’ll consider was first described by Joseph Kruskal in 1956, in the same paper where he rediscovered Jarník’s algorithm. Kruskal was motivated by “a typewritten translation (of obscure origin)” of Borůvka’s original paper that had been “floating around” the Princeton Math department. Kruskal found Borůvka’s algorithm “unnecessarily elaborate.” The same algorithm was rediscovered in 1957 by Harry Loberman and Arnold Weinberger but somehow avoided being renamed after them.

Methodology

Like our earlier minimum spanning tree algorithms, Kruskal’s algorithm has a memorable one-line description:

• Kruskal: Scan all edges by increasing weight; if an edge is safe, add it to $F$.

In the below illustration, Kruskal’s algorithm runs on the example graph. Thick red edges are in $F$; thin dashed edges are useless.

Kruskal’s algorithm for minimum spanning tree

The simplest method to scan the edges in increasing weight order is to sort the edges by weight, in $O(E \log E)$ time, and then use a simple for loop over the sorted edge list. As we will see shortly, this preliminary sorting dominates the running time of the algorithm.

Because we examine the edges in order from lightest to heaviest, any edge we examine is safe if, and only if, its endpoints are in different components of the forest $F$. Suppose we encounter an edge $e$ that joins two components $A$ and $B$ but is not safe. Then, there must be a lighter edge $e^′$ with exactly one endpoint in $A$. But this is impossible, because (inductively) every previously examined edge has both endpoints in the same component of $F$.

Just as in Borůvka’s algorithm, each vertex of $F$ needs to “know” which component of $F$ contains it. Unlike Borůvka’s algorithm, however, we do not recompute all component labels from scratch every time we add an edge. Instead, when two components are ...