aldus.nexus

City power grid

Wire every junction in a real city with the least cable. Prim grows one grid out from your power station; Kruskal lays the shortest cables first and merges colour islands; Borůvka joins every island at once. They always agree on the total.

The numbers

cable laid over the runkm
islands leftlog
cable lengths in the treem
pointer hops per findtallest tree

How it works

The cheapest way to connect everything

Take every junction near the centre of a city as a house that needs power, and every street between two junctions as a place a cable could run, as long as the street. A spanning tree uses just enough cables to join every junction: n junctions need n - 1 cables and no loops, because a loop always has one cable you could drop and still reach everyone. The minimum spanning tree is the one with the least cable in total. On a real street map it usually needs only about half the length of all the streets.

Everything rests on the cut property. Split the junctions into any two groups. Of all the cables that cross between the groups, the shortest one is in a minimum spanning tree: if a tree crossed with a longer one instead, swapping it for the shorter one would join the same groups with less cable. Each algorithm is a different way of choosing cuts.

Prim grows one grid from the power station. The cut is always "the grid against the rest", so it lays the shortest cable leaving the grid, again and again. A binary heap holds the cables on the frontier (the shimmering junctions): each one goes in once and comes out in O(log m), so the whole run is O(m log n). This page uses the lazy version: when a cable comes out of the heap with both ends already powered it is thrown away (the red flashes).

Kruskal sorts every cable by length and walks the list, shortest first (the strip along the bottom of its map). A cable is laid unless both ends are already on the same island, since then it would close a loop. Islands start as single junctions in random colours; when two meet, the smaller takes the larger's colour, with a spark. The sort costs O(m log m) and the loop asks a union-find "same island?" twice per cable.

Union-find keeps each island as a tree of parent pointers; find walks up to the root, union hangs one root under the other. Two tricks keep the trees flat: union by rank hangs the shorter tree under the taller, and path compression points everything a find passed straight at the root. Together a find costs O(α(n)), where α is the inverse Ackermann function: it grows so slowly that it stays at 4 or less for any n that fits in the universe. Untick both in the side panel and watch the trees grow tall.

Borůvka works in rounds: every island picks its own shortest outgoing cable, and all of them are laid at once. Each round at least halves the number of islands, so it needs at most log₂ n rounds, and each round is easy to split across many processors. It is the oldest of the three (1926, to wire up Moravia).

When every cable has a different length the minimum spanning tree is unique, so all three must build the same tree. With ties there can be several trees of the same total: switch the lengths to 25 m drums and Prim and Kruskal often pick different cables, but always lay the same number of drums. As the crow flies, the minimum spanning tree is always inside the Delaunay triangulation of the junctions (the triangles Voronoi city builds with Fortune's sweep), so only those few thousand candidates are needed, not every pair.

The street maps are the ones the shortest path race and the pathfinding playground search, and Prim's frontier is Dijkstra's with one change: a junction's key is the length of its last cable, not of the whole route back to the start. Double every cable of the tree and walk round it, and you have a tour of every junction at most twice as long as the best one: the classic 2-approximation for the travelling salesman, whose solvers race on the same streets.

Greedy is usually a trap, but here the cut property makes every greedy choice safe, and three very different orders all arrive at the same tree.

T* = argmin Σ w(e) over spanning trees Ta tree joining all n junctions with n - 1 cables and the least total length
cut (S, V \ S): the lightest crossing cable is safethe cut property: it belongs to some minimum spanning tree
Prim: O(m log n) · Kruskal: O(m log m) · Borůvka: O(m log n)m candidate cables, n junctions; Kruskal's cost is mostly the sort
find: O(α(n)) amortisedwith union by rank and path compression together; α(n) ≤ 4 for any n that could ever be stored
cable(tour) ≤ 2 · cable(T*) ≤ 2 · cable(best tour)walk round the tree: the travelling salesman's 2-approximation