Minimum Spanning Tree

How to think about it

An MST connects all vertices of a weighted undirected graph at the minimum total edge weight. It is a tree (no cycles) spanning all nodes. The key insight: if you sort edges by weight and add each edge unless it would form a cycle, you get the MST, that is Kruskal. Cycle detection at scale means union-find: two endpoints in the same component → adding the edge makes a cycle, skip it.

Prim grows the MST from a single seed: maintain a min-heap of edges crossing the cut (one endpoint in the tree, one out). Pop the cheapest, add the out node, push its edges. Prim shines on dense graphs (E ~ V²) where sorting all E edges is wasteful. On sparse graphs (E ~ V), Kruskal’s sort + union-find is simpler and equally fast.

Template shapes

Shape	Core move	Example
Kruskal	Sort edges; union-find skip cycles	LC 1135, LC 1584
Prim	Min-heap of crossing edges; grow from seed	LC 1168
MST with constraints	Binary search on answer / filter edges	LC 1489
Offline MST queries	Sort queries + edges; union-find answers	LC 1724

Complexity baseline

Kruskal: O(E log E) (sort) + near-O(E) union-find. Prim with heap: O((V + E) log V). For dense graphs, Prim without a heap is O(V²).

From template to problem

1. Confirm the graph is undirected and weights are comparable (MST does not handle negative specially).
2. Sparse (E ~ V)? Kruskal. Dense (E ~ V²)? Prim.
3. For Kruskal: sort edges, iterate, union-find skip cycles, stop at V-1 edges.
4. The MST minimizes total edge weight, not any individual path, do not confuse with shortest-path.

/** MST template: Kruskal with union-find. */

export function kruskalMST(
  n: number, edges: [number, number, number][],
): { weight: number; edges: [number, number, number][] } {
  const sorted = [...edges].sort((a, b) => a[2]! - b[2]!);
  const parent = new Array<number>(n).fill(0).map((_, i) => i);
  function find(x: number): number {
    if (parent[x] !== x) parent[x] = find(parent[x]!);
    return parent[x]!;
  }
  function union(a: number, b: number): boolean {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
    return true;
  }
  let total = 0;
  const mst: [number, number, number][] = [];
  for (const e of sorted) {
    if (mst.length === n - 1) break;
    if (union(e[0]!, e[1]!)) {
      mst.push(e);
      total += e[2]!;
    }
  }
  return { weight: total, edges: mst };
}

/** MST template: Kruskal with union-find. */

export function kruskalMST(
  n: number, edges: [number, number, number][],
): { weight: number; edges: [number, number, number][] } {
  const sorted = [...edges].sort((a, b) => a[2]! - b[2]!);
  const parent = new Array<number>(n).fill(0).map((_, i) => i);
  function find(x: number): number {
    if (parent[x] !== x) parent[x] = find(parent[x]!);
    return parent[x]!;
  }
  function union(a: number, b: number): boolean {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
    return true;
  }
  let total = 0;
  const mst: [number, number, number][] = [];
  for (const e of sorted) {
    if (mst.length === n - 1) break;
    if (union(e[0]!, e[1]!)) {
      mst.push(e);
      total += e[2]!;
    }
  }
  return { weight: total, edges: mst };
}