Minimum spanning trees
In 1926, Otakar Borůvka was asked to plan the electricity network of southern Moravia as cheaply as possible. His question, how to connect every place using the least total length of line, is the minimum spanning tree problem, and it has some of the simplest and most elegant answers in all of computer science.
The problem
Take a connected graph whose edges have lengths, or costs. A spanning tree is a set of edges that connects all the nodes and contains no cycle; with n nodes it always has exactly n − 1 edges, because each edge connects one more node. Among all spanning trees, a minimum spanning tree has the smallest total length. A graph can have an enormous number of spanning trees, but there is no need to try them all.
Why greedy works
Split the nodes into two groups in any way. The shortest edge that crosses between the groups always belongs to some minimum spanning tree: if a tree used a longer crossing edge instead, swapping it for the shorter one would connect the same nodes for less. This is the cut property. The other side of the coin is the cycle property: the longest edge on any cycle is never needed. Both algorithms below just keep applying these rules.
An example
Take the edges A–B of length 1, B–C 2, A–C 3, C–D 4 and B–D 5. Kruskal's algorithm takes A–B, then B–C, then skips A–C, because A and C are already connected and it would close a cycle, then takes C–D. The tree has three edges for four nodes, so it is done, with total length 7, and B–D is never even looked at. Prim's algorithm from A first adds B by A–B; B's edge B–C (2) beats A–C (3) as the way to C, so C joins by B–C; C's edge C–D (4) beats B–D (5), so D joins by C–D. The same tree, the same 7.
Kruskal, Prim and Borůvka
Kruskal's algorithm, published by Joseph Kruskal in 1956, sorts the edges and uses a union-find structure to skip edges inside one piece, so its work grows with E log E. Prim's algorithm was first described by Vojtěch Jarník in 1930 and rediscovered by Robert Prim in 1957 and Edsger Dijkstra in 1959; with a binary heap its work grows with E log V, and with a simple array with V², which is good for dense graphs. Borůvka's 1926 algorithm lets every piece grab its shortest outgoing edge at the same time, which suits parallel computers.
Uses
Minimum spanning trees design cheap networks of cables, pipes and roads. They group data into clusters: remove the longest edges of the tree and the pieces that remain are the clusters. They give a quick tour for the traveling salesman problem that is at most twice as long as the best one when distances obey the triangle rule. And Kruskal's or Prim's algorithm on a grid with random edge lengths is a classic way to generate a maze.
Explore it
Open the app, choose Kruskal or Prim, and press Step. With Kruskal, the edges still to try are listed under the graph from shortest to longest; edges that would close a cycle are drawn dashed in red. With Prim, the nodes waiting to join are listed with the length of their best edge, which is drawn dashed. Run both on the same graph and compare: the order is different, but the total length is always the same.
Frequently asked questions
How many edges does a spanning tree have?
Exactly one fewer than the number of nodes. Fewer edges could not connect every node, and one more would always create a cycle.
Which is faster, Kruskal or Prim?
Kruskal's algorithm, which sorts the edges, is usually simpler and quick on sparse graphs with few edges. Prim's algorithm with a heap does well on dense graphs, and with a plain array it needs about V² steps no matter how many edges there are.
What is union-find?
A data structure that keeps track of which nodes are in the same piece. It answers "are these two connected?" and merges two pieces almost instantly, which is exactly what Kruskal's algorithm needs for every edge.
Does a minimum spanning tree work for directed graphs?
Not as such. For graphs with one-way edges, the corresponding problem is the minimum spanning arborescence, solved by the Chu–Liu/Edmonds algorithm.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Build a minimum spanning tree