A railway wants to join every town for the least money. It does not need the fastest routes (that was PATH); it needs every town reachable, and nothing paid for twice. The answer is a tree, and the cheapest such tree has properties that make it easy to find.
Joining everything with no loops
Take a connected, undirected graph with a cost on every edge. A spanning tree is a set of its edges that joins every vertex to every other (it spans the graph) and has no loop (it is a tree). A loop would be waste: drop any edge of a loop and everything stays joined, so a cheapest network never has one, as long as costs are not negative.
Step through the first variant of the figure: too few edges leave a vertex out, too many make a loop, and the right number makes a tree.
Five shaded edges, and no loop among them. But G is not joined to anything: 7 vertices need at least 6 edges to be connected.
Three facts about trees
For a graph of V vertices, any two of these three facts about a set of edges give the third:
- it joins every vertex (connected);
- it has no loop;
- it has exactly V − 1 edges.
The reason: start with V vertices and no edges, so V separate parts. Adding an edge either joins two parts (the number of parts drops by one) or lands inside one part (it closes a loop). With no loop, every edge joins two parts, so after k edges there are V − k parts, and one part needs exactly V − 1 edges. This is the counting union-find did in DSUF-5: each successful union is one fewer group.
Two more facts follow, and both are used all through this station:
- One path. In a tree there is exactly one path between any two vertices. Two different paths would make a loop.
- One loop per new edge. Adding one edge u–v to a spanning tree closes exactly one loop: the tree path from u to v, plus the new edge. Removing any edge of that loop gives a spanning tree again.
The cheapest spanning tree
The cost of a spanning tree is the sum of its edges’ costs. A minimum spanning tree (MST) is a spanning tree whose cost is as small as possible. There can be several, all with the same cost, when some edges cost the same; when every cost is different, there is exactly one (lesson 4).
If the graph is not connected, no spanning tree exists. The best one can do is a cheapest tree for each connected part: a minimum spanning forest. Every method in this station gives it with no change.
Negative costs change nothing: only the order of the costs matters (lesson 4 proves this), so adding the same number to every cost gives the same cheapest trees. Compare shortest routes, where adding a number to every cost changes the answer (PATH-3).
The cycle property
Suppose a spanning tree T contains such an edge f, the most expensive on a loop C. Remove f from T: the tree splits into two parts. The rest of the loop C still joins the two ends of f, so some other edge g of C joins the two parts. Add g: a spanning tree again, and it costs w(g) − w(f) less than T, which is below 0 because f is strictly more expensive. So T was not a cheapest tree.
The second variant of the figure uses this in the other direction. Start from any spanning tree. Add an edge that is not in the tree: it closes one loop. If the most expensive edge of that loop is a tree edge, swap it out; the tree gets cheaper. When no outside edge can make a swap like this, every outside edge is the most expensive on its loop. Lesson 4 shows that such a tree is a cheapest one. Making one swap for one new edge is SPAN-P1.
Where spanning trees appear
- Networks. Joining towns by roads or rails, buildings by cables, chips on a board by wires, for the least total length. Otakar Borůvka worked out the first method in 1926 for the electricity network of Moravia.
- Network switches run the spanning tree protocol, so that copies of a message never go round a loop of cables forever.
- Clusters. Building a cheapest tree and then removing its k − 1 most expensive edges splits the points into k groups that are as far apart as possible (lesson 2).
- Approximation. A cheapest spanning tree is the starting point of a classic method that finds a round trip through all cities at most twice the shortest (HARD-4).
Now try SPAN-P1, A cheaper line.
SPAN-1 counts as completed once you step through the figure to the last step.