Minimum Spanning Trees: Kruskal and Prim

When you have to connect several places, each link has a cost: lay fibre between offices, wire up a circuit board, run power to a set of villages. You need everything connected and you want to spend as little as possible.

The result is called a minimum spanning tree. Spanning because it touches every node, tree because it has no cycles, minimum because no other spanning tree costs less.

Why the answer has to be a tree

Before choosing edges it is worth knowing what shape the answer takes, because it removes a lot of guesswork.

Suppose your solution contains a cycle. Then you can delete any one edge of that cycle and everything stays connected, because the rest of the cycle still joins the two ends. You just made it cheaper without losing anything. So a cheapest solution never contains a cycle.

Connected and acyclic is exactly the definition of a tree, which is why the previous page's fact matters here: a tree on n nodes has exactly n - 1 edges. You know in advance how many edges your answer contains, which gives you a clean place to stop.

The greedy idea, and why it's ok

Greedy algorithms usually deserve further analysis. Sometimes greedy algorithms miss better solutions where the value just wasn't notice immediately. So it is fair to be sceptical of a plan that says "keep taking the cheapest edge you can".

Split the nodes into any two groups you like. Look at all the edges crossing between the groups. The cheapest crossing edge is always safe, meaning some minimum spanning tree contains it.

The argument is short. Take any spanning tree that does not use that cheapest crossing edge. Add the edge anyway, and you have created exactly one cycle. That cycle must cross between the two groups a second time somewhere, using some other crossing edge, which by assumption costs at least as much. Delete that one. You still have a spanning tree and it costs no more than before. So there is always a minimum spanning tree containing the cheap edge, and taking it can never be a mistake.

That is the difference between this problem and shortest paths. Here there is a local decision that is provably never wrong. In shortest paths there is not, which is why Dijkstra needs its more careful argument about settling the smallest tentative distance.

Kruskal's algorithm

If cheap edges are safe, the simplest possible plan is to sort every edge by cost and take them in order, skipping any that would close a cycle.

Sorting the edges once and testing each against a cycle check is the whole algorithm. The only real work is answering "would this edge close a cycle?" quickly, which the next section covers. Below is the exact graph this page's numbers use: step through it in Kruskal mode and match each take or skip against the running total.

Notice B-C and B-D being skipped. Neither is expensive. They are rejected purely because their endpoints had already been joined by earlier choices, and adding them would have created a loop for no gain.

The structure that makes it fast

Tracking groups under repeated merging is a small problem of its own, solved by a structure called union-find, or disjoint set union.

Each node points at a parent, and following parents upward lands you at the group's representative, so two nodes are in the same group when they arrive at the same representative. Merging two groups is one pointer assignment.

Left alone, those chains get long and lookups get slow. One cheap fix does most of the work: as you walk up, point each node you pass directly at its grandparent. The chains flatten themselves as a side effect of being used, and the operations end up so close to constant time that the sort dominates the runtime.

Prim's algorithm, the other way round

There is a second approach, and comparing the two is more useful than learning either alone.

Kruskal grows many small fragments all over the graph and eventually merges them, while Prim grows one single blob outward from a starting node. At each step it asks: of all the edges leaving my blob, which is cheapest? Take that one, absorb the node on the far side, repeat.

That is the safe-edge property applied with the two groups being "in my blob" and "everything else". Both algorithms are the same theorem used differently, which is why they always produce a tree of the same total cost even when they pick different edges to get there.

Watch both run

Switch between the two on the same graph you just watched Kruskal solve above. The final total is always identical. What differs is the order the edges get chosen in, and which ones a partial run has already committed to.

Ties, and when the answer is unique

In the trace, A-C and B-C both cost 3. The algorithm took A-C because it came first in the sort, and had the sort ordered them the other way it would have taken B-C instead. Both give a tree costing 11.

That is the general rule. When every edge weight is distinct the minimum spanning tree is unique. As soon as two edges share a weight there can be several different trees of the same minimum cost, and any of them is a correct answer. This catches people out on graded problems, where a checker that compares your edge list against one expected list will reject a perfectly good tree.

The implementation

function kruskal(nodeCount, edges) {
  const parent = Array.from({ length: nodeCount }, (_, i) => i);

  function find(x) {                       // which group is x in?
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];       // flatten as we walk
      x = parent[x];
    }
    return x;
  }

  function union(a, b) {                   // merge two groups
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;           // already together, this edge is a cycle
    parent[ra] = rb;
    return true;
  }

  const sorted = [...edges].sort((x, y) => x.weight - y.weight);
  const tree = [];

  for (const edge of sorted) {
    if (union(edge.from, edge.to)) tree.push(edge);
    if (tree.length === nodeCount - 1) break;   // a tree is full
  }

  return tree;
}

Where it goes wrong

Running it on a disconnected graph. If the graph comes in separate pieces there is no spanning tree at all, and Kruskal will quietly return a forest with fewer than n - 1 edges. Check the count before trusting the result.

Using it for shortest paths. A minimum spanning tree minimizes total cost across the whole network. It does not minimize the distance between any particular pair, and the route between two nodes in an MST is often far from their shortest path. Different question, different algorithm.

Skipping path compression in union-find. It still works and it gets slow, because the chains grow long on large inputs. The one extra line is worth writing every time.

Assuming negative weights are a problem. They are not, here. Nothing in the safe-edge argument assumed weights were positive, so both algorithms handle negative edges without modification. That is a real difference from Dijkstra, and it is worth noticing why: this argument never needed "adding edges cannot make things cheaper".

Check yourself