Kruskal's algorithm
Sort the edges, take the shortest, never close a loop. Kruskal's algorithm is perhaps the simplest greedy algorithm there is, and yet it always finds the cheapest way to connect every node of a graph.
The idea
A minimum spanning tree connects every node of a weighted graph with the smallest possible total edge length. Kruskal's algorithm does not grow one tree from a start. It looks at the whole graph at once, starts with every node as a piece of its own, and keeps joining pieces with the shortest edge available until only one piece is left.
Step by step
Sort the edges from shortest to longest. Try them in that order. If an edge's two ends lie in different pieces, add it to the tree: the two pieces become one. If both ends are already in the same piece, the edge would close a cycle, so skip it. With n nodes the tree is complete after n − 1 edges, and the remaining edges never need to be looked at.
An example
Take the edges A–B of length 1, B–C 2, A–C 3, C–D 4 and B–D 5. Kruskal adds A–B, then B–C, which joins C to the piece A–B. A–C comes next, but A and C are already in one piece, so it would close the cycle A–B–C and is skipped. C–D joins D, and now all four nodes form one tree with three edges, of total length 7. B–D, the longest edge, is never even tried.
Union-find
The only hard question Kruskal's algorithm asks is: are these two nodes already in the same piece? A union-find structure answers it. Each piece is a little tree of links pointing to a representative. Find follows the links to the representative; union links one representative under the other. Path compression, which points every visited node straight at the representative, and union by size keep the links so short that each question takes almost constant time.
History and speed
Joseph Kruskal published the algorithm in 1956, in a short paper in the Proceedings of the American Mathematical Society. Sorting the edges is the slowest part, so the work grows with E log E for E edges. If the edges are already sorted, or their lengths are small whole numbers, it is almost linear.
Explore it
Open the app and press Step. The edges still to try are listed under the graph, shortest first. Each edge that joins two pieces turns green; each edge that would close a cycle is drawn dashed in red. Watch several small pieces grow in different parts of the graph and merge, and notice that the last edges are often never tried.
Frequently asked questions
Why does Kruskal's algorithm sort the edges?
So that every edge it adds is the shortest one that still joins two pieces. That greedy choice is always safe because of the cut property, and every skipped edge is the longest on the cycle it would close, so it is never needed.
What is a disjoint-set structure?
Another name for union-find: a structure that keeps a collection of separate sets, here the pieces of the growing forest, and can tell which set an element belongs to and merge two sets quickly.
Does Kruskal's algorithm work on a disconnected graph?
Yes. It simply ends with one tree for each connected piece of the graph, a minimum spanning forest, because no edge can join pieces that are not connected.
Is Kruskal's algorithm used for anything else?
Stopping it early, before the last pieces merge, groups the nodes into clusters, which is single-linkage clustering. Running it on a grid with random edge lengths generates a maze.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try Kruskal's algorithm