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.