Minimum Spanning Trees: Kruskal and Prim

Here is a concrete problem. You are laying fibre to six towns. You know the cost of every possible cable run between them. You need every town connected, directly or indirectly, for as little money as possible. Which cables do you lay?

That is a minimum spanning tree. Spanning because it reaches every node, tree because it has no cycles, minimum because no other spanning tree costs less.

Why the answer is always a tree

You do not have to take this on faith. Suppose your solution contained a cycle. Then you could delete any one edge from that cycle and everything would still be connected, because the rest of the cycle provides an alternative route. You just saved money for free. So an optimal solution can never contain a cycle, and a connected graph with no cycles is a tree by definition.

This also tells you the answer's shape before you start. A spanning tree over n nodes uses exactly n minus 1 edges. Six towns, five cables. If your MST code returns a different count, it has a bug or the graph was disconnected.

Kruskal: cheapest edge anywhere

Kruskal ignores geography entirely. Sort every edge by cost, cheapest first. Walk down that list and take each edge unless it would close a cycle. Stop when you have n minus 1 of them.

The strange part is that the thing being built is not connected for most of the run. You get scattered clumps that eventually merge. Play the widget below on the Kruskal tab and watch the node colours: each colour is one clump, and taking an edge fuses two clumps into one.

Watch the edge B–E at weight 4. Kruskal considers it and throws it away, because by that point B and E are already in the same clump and adding it would make a loop. The struck-out entry in the edge list is that rejection.

It is easy to assume rejected edges are just the expensive ones, so try the "Cheap triangle" example. A–B costs 1 and B–C costs 2, both taken immediately. Then A–C comes up at only 3, one of the cheapest edges in the whole graph, and it gets thrown out anyway, because A and C are already joined through B. Price has nothing to do with it. The only question Kruskal ever asks is whether the two ends are already in the same group.

The "would this make a cycle" question

Kruskal needs to answer one question over and over: are these two nodes already connected through edges I have taken? Running a fresh traversal every time would be slow. The standard trick is a union-find structure (also called disjoint-set), which does exactly two things: tell you which group a node is in, and merge two groups.

// Each node points at a parent. Follow the chain up and you
// reach the group's representative. Same representative means
// same group, which means adding an edge would close a cycle.

function makeUnionFind(nodes) {
  const parent = new Map(nodes.map((n) => [n, n]));

  function find(x) {
    while (parent.get(x) !== x) x = parent.get(x);
    return x;
  }

  function union(a, b) {
    parent.set(find(a), find(b));
  }

  return { find, union };
}

function kruskal(nodes, edges) {
  const { find, union } = makeUnionFind(nodes);
  const sorted = [...edges].sort((a, b) => a.weight - b.weight);
  const tree = [];

  for (const edge of sorted) {
    if (find(edge.from) === find(edge.to)) continue; // cycle, skip
    union(edge.from, edge.to);
    tree.push(edge);
    if (tree.length === nodes.length - 1) break;     // done early
  }
  return tree;
}

The sort dominates the running time, giving O(E log E). Real union-find implementations add two optimisations, path compression and union by rank, which make find effectively constant time. Look them up when you need the speed, the version above is correct without them.

Prim: grow one blob

Prim comes at it from the opposite direction. Start anywhere. Look at every edge leaving the region you have built so far, take the cheapest one, and swallow whatever node is on the other end. Repeat until everything is inside.

Switch the widget to the Prim tab and replay it. There is only ever one connected blob, growing outward, and no cycle check is needed at all: an edge leaving the blob lands on a node outside the blob by definition, so it cannot close a loop.

function prim(adj, nodes, start) {
  const inTree = new Set([start]);
  const tree = [];

  while (inTree.size < nodes.length) {
    let best = null;

    for (const from of inTree) {
      for (const { to, weight } of adj.get(from) ?? []) {
        if (inTree.has(to)) continue;              // stays inside, ignore
        if (!best || weight < best.weight) best = { from, to, weight };
      }
    }

    if (!best) break;  // graph is disconnected, cannot span it
    inTree.add(best.to);
    tree.push(best);
  }
  return tree;
}

Same total, every time

Run both tabs on the example graph and compare the running total at the end. They match. They pick edges in a different order and can even produce different trees when several edges share a weight, but the total cost is always identical.

Both work for the same underlying reason, usually called the cut property. Take any way of splitting the nodes into two halves. The cheapest edge crossing that divide is always safe to include in some minimum spanning tree. Kruskal applies this globally by always taking the cheapest edge that joins two different groups. Prim applies it locally, with the divide being blob versus everything else. Different bookkeeping, same guarantee.

Which to reach for

Check yourself