Minimum Spanning Trees

If you've ever had to wire up a network, lay fibre between cities, design a circuit board, or cluster a dataset, you've solved a Minimum Spanning Tree problem — even if you didn't call it that. MST is the cheapest way to connect everything with no redundant edges. Two algorithms (Kruskal's and Prim's) solve it in O(E log V) and they're 30-line implementations once you have Union-Find or a heap.

What an MST Actually Is

For a connected, undirected, weighted graph, a spanning tree is a subgraph that:

• includes every vertex,
• is connected,
• contains exactly V − 1 edges (so no cycles).

` A ---5--- B A ---5--- B

Original graph MST (edges 1, 2, 5, 6 → total = 14) `

Note: V−1 edges, no cycles, every vertex reachable.

Daily Mental Model: Laying Fibre Between Cities

You're an ISP and you have to connect 100 cities so that every city has internet, while spending the least amount of fibre. You don't need a direct line between every pair — you just need the network to be connected. That's MST. Adding even one extra edge would form a cycle and waste fibre. Removing any edge would disconnect a city.

Beginner Mistakes to Skip

1. Running Prim/Kruskal on a directed graph. MST is defined for undirected graphs only. The directed analog is "Minimum Arborescence" — Edmonds' algorithm, much harder. 2. Forgetting the "V − 1 edges" stop condition. If you keep adding edges past V − 1 you've stopped building a tree. 3. Naive Union-Find without compression and rank. That's O(V) per find — your O(E log E) Kruskal's becomes O(E·V). 4. Picking the wrong algorithm for the graph density. Kruskal's is dominated by sorting E edges (O(E log E)). Prim's with a heap is O((V + E) log V). On dense graphs (E ≈ V²) Prim's wins; on sparse graphs Kruskal's is usually simpler. 5. Assuming the MST is unique. It's only unique when all edge weights are distinct. Equal weights → multiple MSTs (all with the same total weight). 6. Returning the MST's edges in the order Kruskal's added them and assuming that's a meaningful traversal order. It isn't — Kruskal's order is by weight, not topology.

Intermediate: Kruskal's Algorithm — Sort + Union-Find

`js function kruskal(V, edges) { edges.sort((a, b) => a[2] - b[2]); // sort by weight const uf = new UnionFind(V); const mst = []; let cost = 0; for (const [u, v, w] of edges) { if (uf.find(u) !== uf.find(v)) { // doesn't form a cycle uf.union(u, v); mst.push([u, v, w]); cost += w; if (mst.length === V - 1) break; // tree complete } } return { mst, cost }; } `

The intuition: always pick the cheapest edge that doesn't create a cycle. Cycle detection is what Union-Find is built for.

Complexity: O(E log E) for the sort, plus O(E · α(V)) for Union-Find — total O(E log E).

Intermediate: Prim's Algorithm — Grow From a Vertex

`js function prim(adj, V) { const inMST = new Array(V).fill(false); const pq = new MinHeap(); pq.push([0, 0]); // [weight, vertex] — start at vertex 0 let cost = 0, taken = 0; while (pq.size() && taken < V) { const [w, u] = pq.pop(); if (inMST[u]) continue; // skip stale entries inMST[u] = true; cost += w; taken++; for (const [v, weight] of adj[u]) { if (!inMST[v]) pq.push([weight, v]); } } return cost; } `

The intuition: grow the MST one vertex at a time, always attaching the vertex closest to the current tree. Symmetric to Dijkstra's, but the priority is "distance to the tree" instead of "distance from the source".

Complexity: O((V + E) log V) with a binary heap. With an adjacency-matrix variant (no heap), O(V²) — better on dense graphs.

Intermediate: Kruskal vs Prim Comparison

For interviews, Kruskal's is usually shorter to write *if* you already have a Union-Find class.

Advanced: Union-Find With Both Optimisations

`js class UnionFind { constructor(n) { this.parent = Array.from({length: n}, (_, i) => i); this.rank = new Array(n).fill(0); } find(x) { // path compression if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } union(x, y) { // union by rank const rx = this.find(x), ry = this.find(y); if (rx === ry) return false; if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry; else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx; else { this.parent[ry] = rx; this.rank[rx]++; } return true; } } `

Amortised cost: O(α(n)) where α is the inverse Ackermann function. Concretely: α(n) ≤ 4 for any n you can write down — even n = 10⁸⁰. So in practice, find and union are constant time.

Advanced: The Cut Property — Why Greedy Is Optimal

Cut property: for any cut (any partition of vertices into two non-empty sets), the minimum-weight edge crossing the cut belongs to *some* MST.

Both Kruskal's and Prim's are correct *because* of this. Each time Prim's adds the cheapest edge from "tree-vertices" to "non-tree-vertices", it's adding the minimum edge crossing that cut. Each time Kruskal's adds an edge whose endpoints are in different components, it's adding the minimum edge crossing the cut between those components.

Cycle property (the dual): in any cycle, the maximum-weight edge is *not* in any MST. This justifies "skip the heavier edge that closes a cycle".

Advanced: Boruvka's Algorithm — Parallelisable MST

Predates both Kruskal and Prim (Boruvka, 1926).

1. Each vertex starts as its own component. 2. In parallel, every component picks its cheapest outgoing edge. 3. Add all picked edges to the MST (merging components). 4. Repeat until one component remains.

Each round at least halves the number of components → at most log V rounds → O(E log V). The killer feature: every component's choice in step 2 is independent, so the algorithm parallelises across cores or machines. Used in distributed graph systems.

Advanced: Second-Best MST

Once you have the MST, the second-best MST differs from it by exactly one edge swap:

1. Build the MST. 2. For each non-MST edge \(u, v, w)\: adding it creates a cycle with the MST path between u and v. 3. Find the maximum-weight edge on that path (excluding (u,v) itself). 4. Swapping in (u,v) and removing that max edge gives a candidate. Take the minimum over all such candidates.

With LCA preprocessing, O(E log V) total. Common follow-up question after "find the MST".

Advanced: MST Properties Worth Memorising

• V − 1 edges exactly — by definition.
• Distinct weights ⇒ unique MST.
• Minimax path property: in the MST, the path between any two vertices minimises the *maximum edge weight* — useful for "what's the cheapest bottleneck to connect A and B?".
• Acyclic and connected — that's literally a tree.
• Adding any non-MST edge creates exactly one cycle; removing the heaviest edge of that cycle restores an MST.

Advanced: Real-World Applications

The k-clustering trick is genuinely beautiful — one MST + one sort + drop k−1 edges and you have an optimal max-spacing clustering.

Practice Path

1. Implement Union-Find with path compression AND union by rank. Verify amortised cost by inserting 10⁵ unions and asserting find is sub-µs. 2. Implement Kruskal's MST on a small weighted undirected graph. Print the edges in the order added and verify they are sorted by weight. 3. Implement Prim's MST using a min-heap. Run on the same graph as Kruskal's and verify both return the same total cost. 4. Use Union-Find to count connected components after a stream of unions — useful for "Number of Islands II" / "Friend Circles".