Minimum spanning tree

The formula

The problem statement. Given nodes V, candidate links E, and a cost w(e) on each link:

T* = argmin over spanning trees T of  Σ w(e),  e in T

Reading: out of every possible way to connect all the nodes into one piece with no cycles, pick the one with the smallest total cost — cable feet, trench yards, dollars.

The size of the answer is fixed before you start:

|T| = n − 1     (n nodes always take exactly n − 1 links)

Reading: a tree on n nodes has n − 1 edges, period. If your "minimal" network drawing has more, it has a loop; fewer, and something is disconnected.

The cut property — the reason a greedy method gives the true optimum:

Split V into any two groups. The cheapest edge crossing the split is in the MST.

Reading: however you divide the nodes into two camps, the cheapest wire between the camps belongs in the answer. Its mirror, the cycle property: the most expensive edge on any loop never does.

What the algorithms cost:

Kruskal:  O(E·log E)            sort the edges, take the cheapest that closes no loop
Prim:     O(E·log V)  (heap)    grow one tree outward, always by its cheapest frontier edge

Reading: both are fast enough that problem size is never the excuse — a hundred thousand candidate links sorts in well under a second on a laptop.

Where you meet it

Instrumenting a test stand. Forty thermocouples, a dozen accelerometer blocks, three junction panels, one DAQ rack, and a finite budget of shielded cable and tray space. The candidate edges are the runs your tray layout permits, the weights are cable feet, and the MST is the cheapest trunk plan that lands every channel. The same math prices the conduit before the facilities estimate comes back.
PCB and harness estimation. Before an autorouter has drawn a single trace, the EDA tool prices each net's rat's nest with a spanning-tree (or Steiner) estimate of wirelength. When a review board asks how you know the board will route in four layers, the wirelength number under that claim started life as an MST.
Fiber and network backbone across a facility. Tying a machine shop, a control room, two blockhouses, and an office annex into one LAN: nodes, feasible trench routes, cost per foot. The MST is the floor — the cheapest any fully connected layout can possibly be — and it's the number to hold up against the contractor's bid.
Clustering test data. Single-linkage clustering is the MST wearing a lab coat: build the tree on your data points, cut the longest links, and the pieces that remain are the clusters. It shows up in vibration-signature grouping and outlier screens whether or not anyone says "graph" out loud.

How it works

Both classic algorithms are greedy, and this is one of the few problems in engineering where greedy is provably perfect. Kruskal sorts every candidate edge by cost and walks the list, keeping any edge that doesn't close a loop with the edges already kept. Prim starts at one node and repeatedly grabs the cheapest edge leading out of the tree built so far. The cut property is why neither ever regrets a choice: every edge they take is the cheapest one across some split of the nodes, so it belongs in an optimal answer. No backtracking, no iteration, no tuning.

A concrete run. Six nodes A–F, nine candidate cable routes: A–B 30, A–C 45, B–C 20, B–D 55, C–D 35, C–E 60, D–E 25, D–F 50, E–F 47 (meters). Kruskal walks the sorted list: takes B–C 20, D–E 25, A–B 30, C–D 35, reaches A–C 45 and skips it — A and C are already connected, so it would close a loop — then takes E–F 47 and stops at five edges: total 157 m. The three costlier routes never get a look. Brute-force checking every possible spanning tree confirms 157 m is the minimum. Note the count: six nodes, five cables, as promised.

Why not brute force in general? Cayley's formula says a complete graph on n nodes has n^(n−2) spanning trees. Ten nodes is 10⁸ — annoying. Twenty nodes is 20¹⁸ ≈ 2.6·10²³ — not happening. The greedy algorithms get the exact answer without visiting any of them. For the record, theorists have pushed further: a randomized algorithm with expected linear time (Karger, Klein, and Tarjan, 1995) and Chazelle's 2000 deterministic O(E·α(E,V)) method, where α is an inverse Ackermann function that never exceeds 4 for any input you will ever have ^[1]. On real problems, Kruskal or Prim is the tool.

Now the mistakes, in the order they cost money.

The MST is not a shortest-path tree. It minimizes the sum of all link costs, not the distance between any pair of nodes. In the example above, the tree path from A to F is 157 m of cable, but the graph's shortest A-to-F route is A–C–D–F = 130 m. If what matters is latency or voltage drop from a source to each load, you want Dijkstra's shortest-path tree rooted at the source — a different tree from a different algorithm, and conflating the two is the single most common misuse.

Zero redundancy is a feature of the math and a bug in the design. A tree has exactly one path between any two nodes, so any one cable cut, connector failure, or backhoe splits the network. The MST is the cost floor for connectivity, not a reliability architecture. Closing the tree into a ring costs exactly one more edge and buys survival of any single failure — usually the cheapest insurance on the drawing.

Junction points beat it. The MST only uses the nodes you gave it. Allow a tee in the middle and you can do better: three nodes on an equilateral triangle 100 m on a side cost 200 m by MST, but 173.2 m with a splice at the center — 13.4% saved. The version with free junction points is the Steiner tree problem, and it is NP-hard ^[1], which is why the MST is the tractable proxy everyone actually computes.

Only the ordering of costs matters. Square every weight, convert meters to feet, add margin as a multiplier — the tree doesn't change, because the algorithms only ever ask "which edge is cheaper." That's a free sanity check. But it also marks the model's boundary: the formulation charges each edge independently. If two cables share a trench at a discount, or cost steps when a bundle crosses a wall penetration, the objective is no longer a sum of independent edge weights and the MST answer is no longer optimal.

Ties mean multiple right answers. With distinct edge costs the MST is unique ^[1]; with ties there can be several trees at the same total. Two tools, two orderings, two different drawings — both correct. Check the totals before anyone spends a review-board hour defending one against the other. One more property worth knowing there: every MST also minimizes the single most expensive edge used, so the longest run in the plan is as short as any connected plan can make it ^[1].

History

The problem was born on a power grid, not a blackboard. In 1926 Moravia — the Czech region around Brno — was being electrified, and an engineer friend at the West Moravian power utility put the question to the young mathematician Otakar Borůvka: given the towns and the distances between them, what is the most economical network that reaches them all ^[1]^[2]? Borůvka published the solution that year in two Czech papers, one framed as pure mathematics and one plainly titled as a contribution to economical construction of electrical networks ^[2]^[3]. His method — every fragment simultaneously grabs its cheapest outgoing edge, repeat — still underlies the fastest known MST algorithms ^[2].

In 1930 his countryman Vojtěch Jarník answered with a simpler method in a paper titled "O jistém problému minimálním" — on a certain minimal problem: grow a single tree from one node, always by the cheapest edge leaving it ^[4]^[5]. Then the war and the language barrier buried the Czech work, and the Americans rediscovered everything. Joseph Kruskal published the sort-and-scan method in the Proceedings of the American Mathematical Society in 1956 ^[6]^[7]. Robert Prim, working at Bell Labs on the very Borůvka-shaped problem of pricing connection networks, published Jarník's tree-growing idea in the Bell System Technical Journal in 1957 ^[4]^[8], and Edsger Dijkstra printed it a third time in 1959 ^[4]^[9]. The names stuck to the men who arrived thirty years late. Ronald Graham and Pavol Hell reconstructed the full paper trail — Borůvka first, everyone else after — in their 1985 history of the problem ^[10].

Related tools

/tools/wire-voltage-drop — once the MST fixes the run lengths, size the conductors
/tools/wire-gauge-awg — gauge selection for the runs the tree keeps
/tools/coax-loss — cable-plant losses over the routed lengths
/tools/pipe-pressure-drop — the piping-network version of the same layout question

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →