Minimum Spanning Trees

The 10-second versionCopy Anchor Link

Take a connected, weighted, undirected graph — think towns joined by roads of different lengths. A spanning tree is a set of edges that connects every vertex with no cycles and no leftovers. A minimum spanning tree (MST) is the spanning tree with the smallest total weight — the cheapest set of roads that connects every town. Three greedy algorithms find it: Borůvka's, Kruskal's and Prim's. They look totally different, yet all three are correct because of two exchange properties — the cut property and the cycle property — that pin down exactly which edges are safe to take.

Why this existedCopy Anchor Link

The MST was born from a very concrete 1920s engineering problem: electrifying Moravia.

The Czech region of Moravia needed an electrical grid connecting a set of towns, and the question was brutally practical — which wires do you lay to connect everything for the least total copper? Wires are expensive, and every town must be reachable from every other.

Otakar Borůvka, a young Czech mathematician, solved it in 1926. He didn't call it a "minimum spanning tree" — that name came decades later — but his algorithm, connecting each town to its cheapest neighbour and then merging, is still the fastest way to think about the problem.

The idea was rediscovered and refined by others, sometimes independently:

• 1930 — Václav Jarník gives a "grow from one point" method, the true origin of what many call Prim's algorithm.
• 1956 — Joseph Kruskal publishes the sort-the-edges approach in a short, gorgeous paper, "On the shortest spanning subtree of a graph".
• 1957 — Robert Prim rediscovers Jarník's grow-from-a-seed method; Edsger Dijkstra finds it again in 1959.
• 1961+ — the structure becomes a building block for approximation algorithms and clustering.

Why it mattered then: real infrastructure has a budget, and this was the first clean, provably optimal answer to "connect everything as cheaply as possible." That same question reappears today as cable routing, chip wiring, road planning, and even grouping data points — the MST keeps showing up wherever "connect for least cost" is asked.

Inside the inventor's headCopy Anchor Link

Borůvka is staring at a map of towns and a price list for wire. His instinct is the natural greedy one: each town connects to its nearest neighbour. It feels like it must be optimal — how can ignoring a cheaper wire ever help? — but watch it fail immediately:

Connecting each town to its nearest neighbour gives you small disconnected clumps, not one network. Borůvka's fix is to make that failure the engine: let every little tree reach out and grab the cheapest edge leaving its own cluster, then merge all those choices at once. Each round at least halves the number of clusters, so it all collapses to a single tree in a logarithmic number of rounds.

Then came the insight that explains why any of this works — why greedy is allowed here at all. Greedy is usually wrong, so the fact that it isn't here demands a reason, and the reason is the cut property. Split the vertices into any two groups. Some edges cross between the groups; take the cheapest crossing edge. Borůvka's rule is secretly this rule applied to every cluster at once:

The cut property says the cheapest edge across any cut belongs to some MST. The cycle property is its mirror image: the heaviest edge on any cycle can never be in any MST, because you could always swap it for a lighter edge that reconnects the cycle. Kruskal is the cut property in motion; Prim, Jarník and Borůvka are all just different ways of choosing which cut to look at next.

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

Kruskal's algorithm, the one with the cleanest story — and the one that leans on union-find:

The invariants that make it correctCopy Anchor Link

1. The cut property. For any cut of the vertices, a minimum-weight edge crossing that cut is safe — there exists an MST containing it. This is the theorem that justifies every greedy MST algorithm.
2. The cycle property. For any cycle, the maximum-weight edge on it belongs to no MST. That's exactly why Kruskal can skip any edge whose endpoints are already connected — it would close a cycle, and it's the heaviest on it.
3. The chosen edges always form a forest. We only ever add an edge joining two different components, so no cycle can appear. After V - 1 additions, a forest on V vertices with no cycles must be a spanning tree.
4. Stopping early is safe. Once V - 1 edges are chosen, we have a spanning tree; the cut property guarantees the greedy choices were all correct, so it's a minimum one.

A worked traceCopy Anchor Link

Four towns, five candidate roads. Kruskal sorts them cheapest first and builds the tree:

The chosen tree {0–1, 1–2, 2–3} connects all four towns with total weight 1 + 2 + 4 = 7. The edge 0–2 looked cheap at weight 3, but it would have closed the loop 0–1–2, and the cycle property says the heaviest edge on a cycle is never needed — here it's exactly 0–2. The MST:

It in codeCopy Anchor Link

Kruskal is "sort the edges, then let union-find veto any cycle":

// `edges` is a list of { u, v, w }. Returns the spanning tree and its total weight.function kruskal(n, edges) {  const sorted = [...edges].sort((a, b) => a.w - b.w); // cheapest edges first  const uf = new UnionFind(n);                         // from the union-find page  const mst = [];  let total = 0;  for (const { u, v, w } of sorted) {    if (uf.find(u) !== uf.find(v)) {                   // joining two groups → no cycle      uf.union(u, v);      mst.push([u, v]);      total += w;      if (mst.length === n - 1) break;    }  }  return { mst, total };}

Prim's algorithm attacks the same problem from the other end: instead of sorting edges, grow a single tree from one vertex, always attaching the cheapest edge that reaches a vertex not yet in the tree. With an array to find that cheapest edge, it's a tidy O(V²) — perfect for dense graphs:

// cost[u][v] is the weight of edge u–v, or Infinity if there is none.function prim(cost) {  const n = cost.length;  const inTree = new Array(n).fill(false);  const best = new Array(n).fill(Infinity);         // best[v] = cheapest edge into the tree  best[0] = 0;  let total = 0;  for (let step = 0; step < n; step++) {    let u = -1;    for (let v = 0; v < n; v++)                     // pick the cheapest crossing vertex      if (!inTree[v] && (u === -1 || best[v] < best[u])) u = v;    inTree[u] = true;    total += best[u];    for (let v = 0; v < n; v++)                     // relax edges out of u      if (!inTree[v] && cost[u][v] < best[v]) best[v] = cost[u][v];  }  return total;}

Cost tableCopy Anchor Link

Notice they're all close. Kruskal's cost is dominated by the sort; Prim-with-a-heap is O(E log V) and wins on sparse graphs; plain-array Prim is O(V²) and wins when E is close to V², because its inner loop is dead simple and it skips the log factor. Borůvka's parallel-friendliness — every cluster acts independently each round — is why it shows up in distributed and GPU implementations.

Where you meet it todayCopy Anchor Link

• Network design. Laying fiber, water mains or roads to connect sites for the least cost is the literal Moravia problem, solved by whatever MST algorithm fits the graph's density.
• Clustering. Run the MST, then delete the k - 1 heaviest edges, and you've split the data into k clusters — that's single-linkage clustering, a standard method.
• Image segmentation. Treat pixels as vertices and colour differences as weights; cutting the MST's heavy edges separates regions (the Felzenszwalb–Huttenlocher method).
• Approximation. The MST is the backbone of the 2-approximation for the travelling salesman problem — a cheap skeleton that guarantees a tour within twice the optimum.

That last one is a beautiful, real use. You can't solve TSP exactly for large inputs, but an MST gives you a fast upper bound that's provably within a factor of two:

// Doubling a minimum spanning tree tours every city at cost at most 2× the optimum.function tspUpperBound(dist) {  const n = dist.length;  const edges = [];  for (let u = 0; u < n; u++)    for (let v = u + 1; v < n; v++) edges.push({ u, v, w: dist[u][v] });  return 2 * kruskal(n, edges).total;      // within 2× of the optimal tour}

RecapCopy Anchor Link

• A minimum spanning tree is the cheapest edge set connecting every vertex with no cycles; it's defined only for a connected, weighted, undirected graph.
• Borůvka (1926) grew it from clusters, Kruskal sorts edges and merges, Prim/Jarník grow from one seed with a priority queue.
• Two exchange properties make greedy legal: the cut property (the cheapest edge across a cut is safe) and the cycle property (the heaviest edge on a cycle is useless).
• Kruskal needs union-find to detect cycles; Prim needs a heap to pick the cheapest crossing edge.
• All three run in roughly O(E log V); the choice depends on graph density, not correctness.

Next up: Dijkstra's Algorithm — the same "always take the cheapest frontier" instinct, aimed at shortest paths instead of cheapest trees.