Introduction

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.

Build the Network

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">Five towns, each cable shows its cost. Click an edge to add it,
    click again to remove it. Connect <b>all</b> towns for the <b>lowest total cost</b>,
    with no redundant loops. Checking a network is instant — finding the cheapest is the
    interesting part.</p>
<svg id="map" viewBox="0 0 320 240" class="map" aria-label="town network"></svg>
<div class="status" id="status">Pick cables to connect the towns.</div>
<div class="btns">
  <button id="check" type="button">Check network</button>
  <button id="solve" type="button">Solve (greedy)</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minimum Spanning Tree: connect all towns at the lowest total cable cost.
// Checking a candidate network (connected? total cost?) is a quick scan.
// Finding the cheapest is solved EXACTLY by a greedy rule (Kruskal, 1956):
// sort edges cheap->expensive, add each unless it closes a loop. The cut
// property proves this greedy choice is globally optimal. Runs in P.
const NODES = [
  { id: 0, name: 'A', x: 60,  y: 50  },
  { id: 1, name: 'B', x: 250, y: 55  },
  { id: 2, name: 'C', x: 285, y: 185 },
  { id: 3, name: 'D', x: 120, y: 200 },
  { id: 4, name: 'E', x: 165, y: 120 },
];
// Weighted edges (the optimal MST cost is 24: A-E, E-D, E-B, B-C = 6+7+5+6).
const EDGES = [
  { a: 0, b: 4, w: 6 },   // A-E
  { a: 0, b: 1, w: 9 },   // A-B
  { a: 0, b: 3, w: 11 },  // A-D
  { a: 1, b: 4, w: 5 },   // B-E
  { a: 1, b: 2, w: 6 },   // B-C
  { a: 2, b: 4, w: 8 },   // C-E
  { a: 2, b: 3, w: 12 },  // C-D
  { a: 3, b: 4, w: 7 },   // D-E
];
const SVGNS = 'http://www.w3.org/2000/svg';
const picked = new Set(); // indices into EDGES chosen by the player

function el(tag, attrs) {
  const e = document.createElementNS(SVGNS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]);
  return e;
}
function setStatus(t, cls) {
  const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || '');
}

function render() {
  const svg = document.getElementById('map'); svg.innerHTML = '';
  EDGES.forEach((e, i) => {
    const A = NODES[e.a], B = NODES[e.b];
    const line = el('line', { x1: A.x, y1: A.y, x2: B.x, y2: B.y,
      class: 'edge' + (picked.has(i) ? ' on' : '') });
    const hit = el('line', { x1: A.x, y1: A.y, x2: B.x, y2: B.y, class: 'ehit' });
    hit.addEventListener('click', () => {
      picked.has(i) ? picked.delete(i) : picked.add(i);
      render(); setStatus('Pick cables to connect the towns.', '');
    });
    svg.appendChild(line); svg.appendChild(hit);
    const mx = (A.x + B.x) / 2, my = (A.y + B.y) / 2;
    svg.appendChild(el('rect', { x: mx - 9, y: my - 8, width: 18, height: 14, rx: 3, class: 'wbg' }));
    const t = el('text', { x: mx, y: my + 2, class: 'wlabel', 'text-anchor': 'middle' });
    t.textContent = e.w; svg.appendChild(t);
  });
  NODES.forEach(n => {
    svg.appendChild(el('circle', { cx: n.x, cy: n.y, r: 13, class: 'node' }));
    const t = el('text', { x: n.x, y: n.y, class: 'nlabel' });
    t.textContent = n.name; svg.appendChild(t);
  });
  const total = [...picked].reduce((s, i) => s + EDGES[i].w, 0);
  if (picked.size) setStatus(fmt('Selected %size% cables, total cost %total%.', { size: picked.size, total: total }), '');
}

// Union-find over a set of chosen edges -> components.
function components(edgeIdxs) {
  const parent = NODES.map(n => n.id);
  const find = x => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
  let hadLoop = false;
  for (const i of edgeIdxs) {
    const ra = find(EDGES[i].a), rb = find(EDGES[i].b);
    if (ra === rb) hadLoop = true; else parent[ra] = rb;
  }
  const roots = new Set(NODES.map(n => find(n.id)));
  return { count: roots.size, hadLoop };
}
function totalCost(edgeIdxs) { return [...edgeIdxs].reduce((s, i) => s + EDGES[i].w, 0); }

// Greedy MST (Kruskal): sort edges, add each unless it closes a loop.
function kruskal() {
  const order = EDGES.map((_, i) => i).sort((p, q) => EDGES[p].w - EDGES[q].w);
  const parent = NODES.map(n => n.id);
  const find = x => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
  const tree = [];
  for (const i of order) {
    const ra = find(EDGES[i].a), rb = find(EDGES[i].b);
    if (ra !== rb) { parent[ra] = rb; tree.push(i); if (tree.length === NODES.length - 1) break; }
  }
  return tree;
}
const OPT = totalCost(kruskal());

function check() {
  if (picked.size === 0) { setStatus('No cables yet — pick some edges.', 'bad'); return; }
  const { count, hadLoop } = components(picked);
  const total = totalCost(picked);
  if (count > 1) { setStatus(fmt('✗ Not all towns are connected yet (cost %total%).', { total: total }), 'bad'); return; }
  if (hadLoop) { setStatus(fmt('✗ Connected, but there is a redundant loop (cost %total%). Trim it.', { total: total }), 'bad'); return; }
  if (total === OPT) setStatus(fmt('✓ Connected with no loops — and it is the optimum, cost %total%!', { total: total }), 'ok');
  else setStatus(fmt('✓ Valid spanning tree, cost %total%. The optimum is %OPT% — try Solve.', { total: total, OPT: OPT }), 'ok');
}
function solve() {
  const tree = kruskal();
  picked.clear(); tree.forEach(i => picked.add(i)); render();
  setStatus(fmt('Greedy MST found: cost %OPT% (cheapest possible).', { OPT: OPT }), 'ok');
  console.log('MST edges:', tree.map(i => NODES[EDGES[i].a].name + '-' + NODES[EDGES[i].b].name + '(' + EDGES[i].w + ')').join(' '), '| cost', OPT);
}
document.getElementById('check').addEventListener('click', check);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', () => {
  picked.clear(); render(); setStatus('Pick cables to connect the towns.', '');
});
render();
Result
Console

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.

The Real Complexity

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(Elog⁡V)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/minimum-spanning-tree/Content licensed under CC BY-NC 4.0.