Minimum Spanning Tree Pattern

When to use Minimum Spanning Tree

• The problem asks for the minimum cost to connect every node in a graph — laying cables, building roads, wiring components.
• The graph is undirected, weighted, and you need a connected subset of edges without cycles.
• You need exactly n - 1 edges to span n nodes and minimize the total weight.
• The problem can be modeled as 'pick a subset of pairwise connections to make the graph one connected piece'.
• Variants ask for second-best MST, MST with constraints on certain edges, or MST under updates to the edge list.

Template

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return false;
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}
function kruskalMST(numNodes, edges) {
  edges.sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(numNodes);
  let totalWeight = 0;
  const mstEdges = [];
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      totalWeight += w;
      mstEdges.push([u, v, w]);
      if (mstEdges.length === numNodes - 1) break;
    }
  }
  return mstEdges.length === numNodes - 1 ? totalWeight : -1;
}
function primMST(numNodes, edges) {
  const graph = Array.from({ length: numNodes }, () => []);
  for (const [u, v, w] of edges) {
    graph[u].push([v, w]);
    graph[v].push([u, w]);
  }
  const visited = new Array(numNodes).fill(false);
  const heap = [[0, 0]];
  let total = 0;
  let count = 0;
  while (heap.length > 0 && count < numNodes) {
    heap.sort((a, b) => a[0] - b[0]);
    const [w, node] = heap.shift();
    if (visited[node]) continue;
    visited[node] = true;
    total += w;
    count++;
    for (const [next, weight] of graph[node]) {
      if (!visited[next]) heap.push([weight, next]);
    }
  }
  return count === numNodes ? total : -1;
}

Common mistakes

• Treating Kruskal's union step as cycle-free without actually calling find on both endpoints — adding an edge whose endpoints are already in the same component creates a cycle and breaks the spanning-tree invariant.
• Forgetting that Prim's heap can contain stale entries (a node added at one weight then later at a smaller weight) and processing the larger one first instead of skipping visited nodes on pop.
• Running MST on a disconnected graph and silently returning a forest of n - k edges — always verify that exactly n - 1 edges were selected before returning a result.
• Sorting edges by ascending weight in Kruskal but using a stable in-place sort that mutates the caller's array, causing subtle bugs when the caller reuses the edge list.
• Using MST when the problem actually wants a Steiner tree (subset of terminals must be connected) — these are different problems and MST gives an incorrect lower bound at best.