Minimum Spanning Tree

What a minimum spanning tree actually is

Given a connected, undirected, weighted graph on n vertices, a spanning tree is any subset of n−1 edges that keeps every vertex reachable — connected, acyclic, nothing left out. The minimum spanning tree is the spanning tree whose weights sum to the smallest possible total. Notice what is not being minimised: not the distance between any particular pair of vertices, only the total weight of the whole structure. An MST can easily make the trip from u to v much longer than the graph allows — it only promises the cheapest total wiring.

Why greedy is safe: the cut property

Greedy algorithms usually need a proof before you trust them, and MST has a clean one. Split the vertices into two non-empty groups — call that a cut. The cut property says: the cheapest edge crossing that cut belongs to some MST. The intuition is an exchange argument. Suppose an MST T doesn't contain that cheapest crossing edge e. Add e to T anyway — now you have a cycle, and that cycle has to cross back over the cut on some other edge f. Since e was the cheapest crossing edge, weight(e) ≤ weight(f), so swapping f out for e leaves you with a spanning tree that is no heavier. The greedy choice was never a mistake.

The mirror image is the cycle property: on any cycle, the single heaviest edge is never needed — you can always delete it and stay connected. These two facts are the same fact seen from opposite ends, and they generate the two classic algorithms. Kruskal thinks in cycles ("take the cheapest edge unless it closes a cycle"), Prim thinks in cuts ("keep taking the cheapest edge leaving the tree I've built so far").

On uniqueness: if all edge weights are distinct, the MST is unique — the exchange argument above becomes a strict inequality and no swap can tie. With ties, several different MSTs can exist, but every one of them has the same total weight. That's the honest answer to "is the MST unique?" in an interview: the tree may not be, the cost always is.

Kruskal's algorithm: sort every edge, take it if it doesn't close a cycle

Kruskal is the cycle property applied greedily. Sort all E edges by weight, walk them cheapest first, and accept an edge only when its two endpoints are currently in different components. "Different components?" is exactly the question the union-find structure from the previous chapter answers in near-constant time — here is a compact version with path halving and union by rank so this file stands alone.

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // path halving — flatten as we climb
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false; // already connected — this edge would close a cycle
    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
    return true;
  }
}

// edges: [u, v, weight][] with 0-indexed vertices — O(E log E) time, O(V) extra space
function kruskalMST(n, edges) {
  edges.sort((a, b) => a[2] - b[2]); // the sort IS the algorithm's cost

  const dsu = new DSU(n);
  const tree = [];
  let total = 0;

  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) { // union returns false when u and v already share a root
      tree.push([u, v, w]);
      total += w;
      if (tree.length === n - 1) break; // n-1 edges = spanning, stop early
    }
  }

  // fewer than n-1 accepted edges means the graph was disconnected
  return tree.length === n - 1 ? { total, tree } : null;
}

Complexity is O(E log E) dominated entirely by the sort — the union-find work is O(E · α(V)), and the inverse Ackermann function α is below 5 for any input that fits in memory, so treat it as constant when you say the number out loud. Space is O(V) for the DSU (the edge list is given, not built). Since E ≤ V², log E ≤ 2 log V, so you'll also see this written O(E log V) — same thing.

Watching Kruskal build the tree, edge by edge

Running it on the graph above, with edges sorted 1, 2, 3, 4, 5, 6, 7:

Prim's algorithm: grow one tree outward with a heap

Prim keeps a single growing tree instead of a forest. At each step the cut is "vertices in the tree" versus "vertices outside," and the cut property says to take the cheapest edge crossing it. A min-heap keyed by edge weight produces that edge in O(log E). Here is a compact binary heap of [weight, from, to] triples so the code below runs as written.

class MinHeap {
  constructor() { this.a = []; }
  get size() { return this.a.length; }
  push(item) {
    const a = this.a;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      for (let i = 0; ; ) {
        const l = 2 * i + 1, r = l + 1;
        let s = i;
        if (l < a.length && a[l][0] < a[s][0]) s = l;
        if (r < a.length && a[r][0] < a[s][0]) s = r;
        if (s === i) break;
        [a[s], a[i]] = [a[i], a[s]];
        i = s;
      }
    }
    return top;
  }
}

// adj[u] = [[v, weight], ...] — O(E log V) time, O(E) space for the heap
function primMST(n, adj) {
  const inTree = new Array(n).fill(false);
  const heap = new MinHeap();
  const tree = [];
  let total = 0;

  inTree[0] = true; // seed with any vertex — MST is the same regardless of start
  for (const [v, w] of adj[0]) heap.push([w, 0, v]);

  while (heap.size > 0 && tree.length < n - 1) {
    const [w, u, v] = heap.pop();
    if (inTree[v]) continue; // STALE entry — v got absorbed by a cheaper edge already

    inTree[v] = true;
    tree.push([u, v, w]);
    total += w;

    for (const [next, nw] of adj[v]) {
      if (!inTree[next]) heap.push([nw, v, next]); // only frontier edges matter
    }
  }

  return tree.length === n - 1 ? { total, tree } : null;
}

Prim also gives the wrong answer silently on a disconnected graph: it fills one component and stops. Kruskal, by contrast, naturally produces a minimum spanning forest — one tree per component. If the input might be disconnected and you're using Prim, you must loop over unvisited seeds yourself, or check tree.length === n - 1 as above.

Kruskal vs Prim: which one in the interview

The one that actually decides interviews is the last row of the dense column. When the graph is implicit and complete — "n points, cost between any two is their distance" — materialising all V²/2 edges to sort them is the mistake. With V = 1000 that's half a million edges to build and sort when O(V²) Prim never stores a single one.

Min Cost to Connect All Points — the dense case done right

The classic version: given points on a plane, connecting two costs their Manhattan distance, connect them all as cheaply as possible. Every pair is an edge, so this is a complete graph — reach for O(V²) Prim, which keeps one number per vertex ("cheapest known edge from the tree to you") and rescans instead of heaping.

// O(V²) time, O(V) space — never builds the edge list at all
function minCostConnectPoints(points) {
  const n = points.length;
  const minDist = new Array(n).fill(Infinity);
  const inTree = new Array(n).fill(false);
  minDist[0] = 0; // start vertex costs nothing to attach
  let total = 0;

  for (let step = 0; step < n; step++) {
    // pick the cheapest vertex still outside the tree — this is the cut property
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!inTree[v] && (u === -1 || minDist[v] < minDist[u])) u = v;
    }

    inTree[u] = true;
    total += minDist[u];

    // relax: u joining the tree may give every outsider a cheaper attachment
    for (let v = 0; v < n; v++) {
      if (inTree[v]) continue;
      const d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
      if (d < minDist[v]) minDist[v] = d;
    }
  }
  return total;
}

The relax step is why this works without a heap: minDist[v] is always "cheapest edge from the current tree to v," so scanning it for the minimum is finding the cheapest edge across the cut. That linear scan costs O(V) per step for O(V) steps — the same O(V²) as building the matrix, so the heap buys nothing.

The virtual-node trick, and other MST disguises

MST problems rarely announce themselves. A recurring twist: each node has a standalone cost as well as connection costs — "each village can dig its own well for cost w[i], or lay a pipe to another village for cost c." That looks like it isn't a spanning tree at all, until you add a virtual node 0 representing "the water source" and connect it to village i with weight w[i]. Now "dig a well" is just another edge, and a plain MST over n+1 nodes is the answer.

function minCostToSupplyWater(n, wells, pipes) {
  // vertex 0 is virtual: edge 0→i with cost wells[i-1] means "dig a well at i"
  const edges = pipes.slice();
  for (let i = 0; i < n; i++) edges.push([0, i + 1, wells[i]]);

  const result = kruskalMST(n + 1, edges); // n+1 vertices now, so n edges in the tree
  return result.total;
}

Two more disguises worth recognising instantly. "Remove the maximum number of edges while keeping the graph connected" → build an MST, the answer is E − (V−1). "Minimise the largest edge on a path between all pairs" → the MST is also a minimax spanning tree, so the answer is the heaviest edge on the MST path, not a shortest-path computation.

Recognizing it in an unseen problem

• "Connect all," "minimum cost to link every," "cheapest network/wiring/roads," "keep everything reachable" — total cost over the whole structure, not a route between two nodes
• The graph is undirected and weighted. MST is undefined on a directed graph — that's the arborescence / Chu-Liu-Edmonds problem, and no interviewer expects it
• Brute force would enumerate spanning trees — Cayley's formula says a complete graph on n vertices has nⁿ⁻² of them, so exhaustive search is hopeless and greedy is the whole point
• Distinguish from Dijkstra: if a source vertex is named, or the answer is "distance from A to B," it's shortest paths, not MST
• Distinguish from plain union-find connectivity: if weights are ignored and the question is just "are these connected / how many components," you need the DSU but not the sort
• Per-node costs alongside per-edge costs → add a virtual node and turn the node cost into an edge cost
• Complete/implicit graph on ≥ ~1000 points → O(V²) Prim; explicit sparse edge list → Kruskal