🧠 Mental Model
An MST connects all vertices with the minimum total edge weight and no cycles.
Kruskal's is the "global greedy": sort all edges by weight, then add each edge unless it
would form a cycle. Union-Find (Days 8–10) is exactly the cycle test.
The elegance: you never think about the tree's shape. You just repeatedly grab the globally cheapest
edge that keeps things acyclic. The forest gradually merges into one tree.
⚙️ Mechanics
- Sort edges ascending by weight.
- Init Union-Find with each vertex in its own set.
- For each edge (u, v, w): if find(u) ≠ find(v), accept it and
union; else skip (would cycle).
- Stop once V−1 edges are accepted — the MST is complete.
📐 Correctness — the Cut Property
Cut Property
For any partition (cut) of the vertices into two non-empty sets, the minimum-weight edge
crossing the cut belongs to some MST. (With distinct weights, it's in every MST.)
Proof (exchange argument)
Let e = (u,v) be the lightest edge crossing a cut, and suppose some MST
T excludes it. Adding e to T creates a cycle; that
cycle must cross the cut a second time via another edge e'. Since e
is the lightest crossing edge, w(e) ≤ w(e'). Swap: T' = T − e' + e
is still a spanning tree and w(T') ≤ w(T), so T' is also an MST —
and it contains e. ∎
Why Kruskal is correct: when it accepts the cheapest edge joining two different
components, consider the cut separating one component from the rest. That edge is the lightest crossing
it (all cheaper edges were already processed and lie within components), so by the cut property it's
safe — it belongs to an MST.
📊 Complexity
| Step | Cost |
|---|
| Sort edges | O(E log E) = O(E log V) |
| Union-Find ops | O(E · α(V)) ≈ O(E) |
| Total | O(E log E) — dominated by the sort |
Kruskal favors sparse graphs (few edges → cheap sort). For dense graphs, Prim's with an adjacency matrix (Day 14) can win.
💻 Reference Implementation (Java)
Reuses the optimized Union-Find from Day 9.
import java.util.*;
/** Kruskal's MST. edges = {u, v, w}. Returns total weight, or -1 if disconnected. */
public int kruskal(int n, int[][] edges) {
Arrays.sort(edges, (a, b) -> a[2] - b[2]); // ascending weight
UnionFind uf = new UnionFind(n); // Day 9 class
int total = 0, used = 0;
for (int[] e : edges) {
if (uf.union(e[0], e[1])) { // true ⇒ no cycle ⇒ safe edge
total += e[2];
if (++used == n - 1) return total; // spanning tree complete
}
}
return -1; // fewer than n-1 edges ⇒ graph not connected
}
🎭 Problem Variances — how Big Tech disguises MST
| Disguise / phrasing | What's really asked | Twist to handle |
|---|
| "Min cost to connect all points/cities/nodes" | Plain MST total weight | Often complete graph → build all pairwise edges (Manhattan distance, etc.) |
| "Connect houses to water (virtual node)" | MST with a super-source | Add node 0 with edges = well costs, then MST |
| "Some edges already built (free)" | MST with pre-unioned components | Union the free edges first (weight 0), then Kruskal the rest |
| "Critical / pseudo-critical edges" | Which edges are in ALL / SOME MSTs | Run MST excluding/forcing each edge; compare weights |
| "Maximum spanning tree" | Same greedy, reversed | Sort descending |
| "Minimize the max edge on a path" (bottleneck) | Minimum bottleneck spanning tree | MST minimizes the max edge too — Kruskal order gives it |
| "K components remaining / remove costliest links" | Stop MST early | Take only V−k safe edges (leaves k clusters) |
Recognition heuristic: "connect everything at minimum total cost, no redundancy" = MST. If it's a complete/geometric graph, the work is generating the edge list before Kruskal.
⚠️ Common Pitfalls
Not checking connectivity: if fewer than V−1 edges are accepted, no spanning tree exists. Return −1 / handle it.
O(V²) edges on geometric problems: "connect all points" builds every pair — fine for small n, but consider Prim's for dense inputs.
Overflow on summed weights: large weights × many edges → use long.
🎯 Problems
LC 1584
Min Cost to Connect All Points
Complete graph on points; edge weight = Manhattan distance. Generate edges, then Kruskal.
Med
LC 1135
Connecting Cities With Minimum Cost
Textbook MST; return −1 if the graph can't be fully connected.
Med
LC 1489
Find Critical and Pseudo-Critical Edges in MST
Hard MST variance — compare MST weight with each edge forced-in vs excluded.
Hard
📚 References
- CLRS, 3rd ed., §23.1–23.2 — MST generic method, cut property (Theorem 23.1), Kruskal's algorithm.
- Kruskal, J. B. (1956) — "On the shortest spanning subtree of a graph," Proc. AMS 7(1), 48–50.
- Tarjan, Data Structures and Network Algorithms (1983) — MST + disjoint sets together.