Minimum Spanning Tree

01 / The shared mechanism

A minimum spanning tree is the cheapest way to connect every node of a weighted, undirected graph — exactly N − 1 edges, no cycles, minimum total weight. Two classic ways to grow it: Kruskal walks the edges sorted by weight and uses union-find to skip any edge that would close a cycle. Prim starts at one node and uses a min-heap to repeatedly absorb the lightest edge crossing the current tree.

01 / The one-sentence essence
Sort the edges by weight ascending, then sweep through them and accept each edge whose endpoints lie in different components (a Union-Find query); skip the rest — they'd close a cycle. Stop after N − 1 acceptances.
Problembuild the minimum spanning tree via Union-FindV6E8
43124265012345edges sorted by weightedge · w0 — 140 — 231 — 211 — 322 — 343 — 424 — 563 — 55
Graph: 6 nodes, 8 edges. We need 5 edges to span them.
step
0 / 16
accepted
0 / 5
total weight
—
0 / 16

02 / The pattern signature

# input: V nodes, edges = [(u, v, w), …]sort(edges) by w ascparent[i] ← i # DSU initmst ← []; total ← 0for (u, v, w) in edges:if find(u) ≠ find(v): # different componentsunion(u, v); mst.push((u, v, w)); total += wif len(mst) == V − 1: break# else: u, v already connected → skip (would close a cycle)return total if len(mst) == V − 1 else ∞ # disconnected

03 / When to recognize this pattern

"minimum spanning tree"
The canonical phrasing. Whenever a problem hands you a weighted undirected graph and asks for the cheapest connected subgraph — that's an MST. Kruskal is the right tool when the input is already an edge list.
"connect all nodes cheaply"
LC 1135 (Connecting Cities With Minimum Cost). The cost of connecting all N cities equals the weight of the MST. Sort the connection costs, run Kruskal, return the total — or −1 if fewer than N − 1 edges were accepted.
"second-best MST"
LC 1489 (Critical and Pseudo-Critical Edges). Build the MST once, then for each edge ask: can we still hit the same total weight if we force-exclude this edge? force-include it? Two extra Kruskal passes per edge cleanly classify every edge as critical, pseudo-critical, or neither.
"min cost to connect points"
LC 1584. Build the complete graph (Manhattan distance between every pair), sort all O(N²) edges, and run Kruskal. For dense graphs this is where you compare Kruskal's edge-centric cost against Prim's adjacency-list approach — Prim with a heap usually wins here.

04 / Common pitfalls

i.
Forgetting to stop at N − 1 edges.
Once you've accepted N − 1 edges the tree is complete — keep iterating and you waste time on doomed find/union calls. Worse, on a problem variant where the "edge cost" isn't purely additive (e.g. budget constraints, alternate tie-breaks) the extra iterations can quietly produce wrong answers. Break early.
ii.
Union-Find without path compression.
Kruskal's time is dominated by sorting at O(E log E), but only if each find/union is near-constant. Skip path compression (or union-by-rank) and a long chain turns into O(N) per find — your Kruskal degrades to O(E · N). The DSU optimizations aren't optional flair; they're load-bearing.
iii.
Confusing MST with Shortest Path.
Both are graph algorithms about "minimum" — but they minimize different things. MST minimizes the total weight of a tree spanning all nodes; shortest path minimizes the path weight from one node to another. The tree edge between two nodes in the MST is generally not the shortest path between them. Different invariant, different algorithm.

05 / Go practice — on LeetCode

Four problems. The first two are pure Kruskal warm-ups. Min Cost to Connect All Points is the dense-graph case where you weigh Kruskal vs Prim. Critical Edges turns Kruskal into a subroutine — the algorithm becomes a primitive.

01Connecting Cities With Minimum Cost— LC 1135medium→02Min Cost to Connect All Points— LC 1584medium→03Optimize Water Distribution in a Village— LC 1168hard→04Find Critical and Pseudo-Critical Edges in MST— LC 1489hard→

— / When to use which

Kruskal
Use when the graph is given as an edge list and you already lean on a Union-Find structure — sort edges by weight, walk through, accept any edge whose endpoints are in different components. Edge-centric; needs no adjacency at all.
edge list + union-find · LC 1135 · LC 1489
Prim
Use when the graph is given as an adjacency list or the edge count is quadratic in N (dense graph). Start at any node, push its outgoing edges into a min-heap, repeatedly pop the cheapest edge that lands on an unseen node. Node-centric; the tree grows from a seed.
adjacency + min-heap · LC 1168 · LC 1584