Chapter 11 · Advanced Tree Algorithms
Minimum Spanning Tree
Kruskal, Prim, and Borůvka from one lemma; the cut property, the exchange argument, and what each algorithm is actually for.
#The cut property
For a connected weighted undirected graph, a minimum spanning tree is a spanning tree T minimising ∑e ∈ T w(e). Write MST(G) for its weight. With equal weights it is just "any spanning tree"; with {0,1} weights it is "the fewest expensive edges".
Let ∅ ≠ S ⊊ V and let e = (u,v) be a minimum-weight edge crossing the cut (S, bar S). Then some MST contains e. If e is the unique lightest crossing edge, every MST contains it.
Take any MST T. If e ∈ T, done. Otherwise T + e has exactly one cycle, and that cycle crosses the cut at least twice, so it contains another edge f crossing (S,bar S) with w(f) ≥ w(e). Then T' = T - f + e is a spanning tree (removing f breaks the only cycle) with wt(T') ≤ wt(T), so T' is minimum and contains e. If w(f) > w(e), T was not minimal — contradiction, which proves the uniqueness claim. ∎
- Kruskal considers edges by increasing weight and keeps every edge that connects two components: when it accepts e joining A,B, e is lightest across the cut (cup A, V ∖ cup A) among remaining edges, so the lemma applies to that cut — accept.
- Prim grows one component S and takes the lightest edge leaving it: exactly the lemma with that S.
- Borůvka takes, for every component, its lightest outgoing edge: 2i rounds merge components pairwise, since each accepted edge is the lightest across its component's cut.
- Reverse-delete (sort decreasing, delete an edge if the graph stays connected, else it is in every MST by the cycle property) is the dual argument.
#Kruskal, and why it is the default
struct Edge { int u, v, w; };
sort(e.begin(), e.end(), [](auto &a, auto &b) { return a.w < b.w; });
DSU dsu(n);
long long mst = 0; int cnt = 0;
for (auto &[u, v, w] : e)
if (dsu.unite(u, v)) { mst += w; if (++cnt == n - 1) break; }
// mst is the answer iff cnt == n - 1, else the graph was disconnected#The four algorithms compared
The three, compared
| time | needs | wins on | |
|---|---|---|---|
| Kruskal | O(m log m) | sort + DSU | sparse graphs, parallel/external MST, "second-best MST", MST of a graph given as an edge list |
| Prim (binary heap) | O(m log n) | adjacency + priority_queue | dense-ish graphs; simple to write |
| Prim (array, no heap) | O(n2) | adjacency matrix | dense graphs, m = Θ(n2) — the heap only adds log factors there |
| Borůvka | O(m log n), O(m) with linear-time min-search per round | components only | the choice when edges are generated implicitly (e.g. nearest-neighbour MST in a metric, Euclidean MST via Voronoi) — each round scans all edges once with no sorting |
#Two more properties
- Cycle property: on any cycle, the heaviest edge (if unique) is in no MST. Proof: exchange it with a lighter edge of the cycle.
- MST sensitivity / replacement edges: for a non-tree edge e, adding it to T and deleting the heaviest edge on the T-path between its endpoints gives the best tree using e; so "the second-best MST" = minimum of that over non-tree edges, computable in O(m log n) with Heavy-Light Decomposition or O(n2) with a path-max table.
- Bottleneck property: an MST minimises the maximum edge on the path between every pair of vertices among all spanning trees, so MST answers minimax-path queries: the lightest possible "capacity ceiling" from s to t is the max edge on the MST path (Kruskal also gives you this as "the weight of the edge that first connected s and t").
Switch between Kruskal and Prim on the same weighted graph. The rejected edges are the ones the cut property forbids: watch a heavy edge get skipped because its endpoints are already connected — that is the cycle property doing the rejecting.
While running Kruskal, when edge e merges components A and B, create a new node x with children root(A), root(B) and weight w(e), and make x the merged component's representative (DSU with explicit roots, Disjoint Set Union (Union–Find)). The result is the Kruskal reconstruction tree: n + (n-1) nodes, and lca(u,v) in it has weight = the minimax value between u and v. Every query "smallest W such that u,v are connected using edges ≤ W" is then one LCA (and "the set of vertices reachable from u with edges ≤ W" is the subtree of the highest ancestor of u of weight ≤ W — flatten with tin and answer with a Fenwick). This is how "flood fill / connectivity threshold" problems are solved offline: the union tree turns them into subtree queries.
#Directed MST is another problem
Everything above is undirected. A minimum arborescence (rooted out-branching of minimum cost) needs Chu–Liu/Edmonds: repeatedly contract the cycle formed by each vertex's cheapest incoming edge, in O(nm). It is not Kruskal with a direction: the greedy fails because a directed cut does not give a cycle to exchange along. See Max Flow: Ford–Fulkerson, Dinic, Push–Relabel for how orientation constraints are handled by flow instead.