Minimum Spanning Tree

Imagine you run a small electric company. There are five villages on the map and you must lay cable so that every village can reach every other — directly or through the others. Each possible cable has a price tag that depends on distance and terrain. You don't care how the network looks; you only want the total cost to be as small as possible.

That is the Minimum Spanning Tree problem. "Spanning" means it touches every village; "tree" means it has no wasteful loops (a loop would mean you paid for a cable you could cut without disconnecting anyone). Among all the ways to connect everything, you want the cheapest.

It feels like it should be hard — the number of possible networks grows explosively with each village. But this is one of the happy corners of computer science where a dead-simple, almost greedy strategy gives you the provably perfect answer, every time.

Below is a map of 5 towns with the cost of every possible cable written on it. Click an edge to add it to your network; click again to remove it. Your goal: connect all towns at the lowest total cost, with no redundant loops.

<p class="hint">{{hint}}</p>
<svg id="map" viewBox="0 0 320 240" class="map" aria-label="{{map_aria}}"></svg>
<div class="status" id="status">{{status_pick}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.map { width: 100%; max-width: 420px; height: auto; display: block;
       background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px; }
.edge { stroke: #b9c4cf; stroke-width: 5; cursor: pointer; }
.edge:hover { stroke: #8fa3b5; }
.edge.on { stroke: #2a9d8f; }
.edge.mst { stroke: #2a9d8f; }
.ehit { stroke: transparent; stroke-width: 16; cursor: pointer; }
.wlabel { font: 700 11px ui-monospace, monospace; fill: #1d3557; pointer-events: none; }
.wbg { fill: #fff; opacity: .85; pointer-events: none; }
.node { fill: #1d3557; }
.nlabel { font: 700 12px system-ui, sans-serif; fill: #fff; text-anchor: middle;
          dominant-baseline: central; pointer-events: none; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a network is easy: add up the cable costs and confirm everything is connected. Finding the cheapest one by hand means weighing many trade-offs at once. Press Solve (greedy) and watch the algorithm do something almost suspiciously simple: sort the cables from cheapest to most expensive and add each one unless it would create a loop. That's Kruskal's algorithm, and the tree it builds is guaranteed to be the cheapest possible.

Here is the good news: unlike many problems we cover, the Minimum Spanning Tree is easy — it sits firmly in P, the class of problems with efficient algorithms.

• Brute force would try every subset of cables that connects everything — and the count grows faster than exponentially with the number of towns. Hopeless beyond a handful of nodes.
• The greedy rules work, and they are fast. Kruskal's algorithm (Joseph Kruskal, 1956) sorts the edges and adds the cheapest that doesn't form a loop, using a union-find structure to detect loops instantly. Prim's algorithm (Robert Prim, 1957; earlier Vojtěch Jarník, 1930) grows the tree outward one nearest node at a time. Both run in about $O(E \log V)$ time — a few cables times the logarithm of the towns.
• Why greed is correct. The cut property says: if you split the towns into two groups, the single cheapest cable crossing the gap must belong to some minimum spanning tree. The cycle property says the most expensive cable in any loop can always be dropped. Together they prove that never-create-a-loop greed reaches the global optimum — no backtracking, no guessing.
• A surprising history. The first MST algorithm was published by Otakar Borůvka in 1926, to electrify Moravia — making this one of the oldest algorithms in the field.

This is the bright mirror image of problems like the Traveling Salesman: connecting all the towns is easy, but visiting all of them in the shortest tour is NP-hard. One small change in the question flips it from trivial to intractable.

"Connect everything as cheaply as possible" describes a remarkable number of real tasks, and the MST is the standard tool:

• Infrastructure: laying power lines, water pipes, fiber-optic cable or roads so every location is reachable for the least total cost — exactly Borůvka's original electrification problem.
• Computer networks: designing low-cost backbones and broadcast trees that touch every node without redundant links.
• Clustering and machine learning: building an MST over data points and cutting its most expensive edges is a classic way to discover natural groups (single-linkage clustering).
• Image segmentation: treating pixels as nodes, MST-based methods separate an image into coherent regions.
• Approximation engines: the MST is the starting point for fast, near-optimal heuristics for harder problems like the Traveling Salesman and the Steiner tree.

Learn the minimum spanning tree and you've met one of the cleanest success stories in algorithms — a place where the obvious greedy move happens to be the perfect one.

The Minimum Spanning Tree is a reminder that not every problem that looks hard is hard. The space of possible networks explodes, yet a rule a child could follow — always take the cheapest cable that doesn't close a loop — lands exactly on the optimum, with a clean mathematical proof behind it.

So the next time you see fiber being trenched along a road or a power line crossing a valley, remember there's a near-century-old algorithm deciding where it goes. And notice the knife-edge: connect every town and it's easy; tour every town and you fall straight into P vs NP. The whole drama of complexity often hides in a single word of the question.