Minimum Spanning Tree

A spanning tree connects all $n$ vertices with $n-1$ edges. The minimum spanning tree minimises total edge weight. For a disconnected graph you get a minimum spanning forest.

The two properties that make greedy work

Cut property. For any partition of the vertices into two sets, the lightest edge crossing the cut belongs to some MST. (If unique, it belongs to every MST.)

Proof: take an MST not containing that edge $e$. Adding $e$ creates a cycle, which must cross the cut again at some edge $f$ with $w(f)\ge w(e)$. Swapping $f$ for $e$ gives a spanning tree of no greater weight. ∎

Cycle property. For any cycle, the heaviest edge on it is not in any MST (if strictly heaviest).

Between them, these justify every MST algorithm: Kruskal uses the cut property globally, Prim uses it locally, Borůvka uses it per component.

The algorithms

Kruskal — $O(E\log E)$

Sort edges by weight; add an edge if its endpoints are in different DSU components.

sort(edges.begin(), edges.end(), [](auto& a, auto& b){ return a.w < b.w; });
DSU dsu(n);
long long total = 0;
for (auto& [w, u, v] : edges)
    if (dsu.unite(u, v)) total += w;

Simplest to write and the right default. See Kruskal’s Algorithm.

Prim — $O(E\log V)$ with a heap, $O(V^2)$ with an array

Grow one tree, always adding the cheapest edge leaving it. The $O(V^2)$ array version is better for dense graphs ($E\approx V^2$). See Prim’s Algorithm.

Borůvka — $O(E\log V)$

Every component simultaneously picks its cheapest outgoing edge; merge; repeat. Components at least halve each round. Parallelisable, and the basis of every asymptotically faster MST algorithm. See Borůvka.

Choosing

Situation	Algorithm
General case	Kruskal
Dense graph, $E\approx V^2$	Prim with an array, $O(V^2)$
Edges already sorted, or weights are small integers	Kruskal with counting sort, $O(E\alpha )$
Parallel / distributed	Borůvka
Directed graph (arborescence)	Chu-Liu/Edmonds — Kruskal and Prim are wrong here
Geometric points	build the Delaunay triangulation first — the EMST is a subgraph, so $O(n)$ edges instead of $O(n^2)$

Facts worth knowing

• If all edge weights are distinct, the MST is unique.
• The MST minimises the maximum edge as well as the sum — so it is also the minimum bottleneck spanning tree. The converse fails.
• The path between $u$ and $v$ in the MST minimises the maximum edge over all $u$-$v$ paths. This turns bottleneck queries into path-max queries on a tree.
• The maximum spanning tree is the MST with negated weights.
• MSTs of $G$ and of $G$ with every weight transformed by a strictly increasing function are the same tree.
• The set of MSTs forms the bases of a matroid, which is precisely why greedy is optimal.

Common variants

Variant	Approach
Second-best MST	for each non-tree edge, swap it for the max edge on its tree path; take the best swap
Minimum bottleneck spanning tree	the MST already is one
MST with one edge forced in	contract it, then MST the rest
MST with one edge forced out	delete it, then MST
MST after an edge weight decreases	add it, remove the max edge on the cycle it creates
Count MSTs	group edges by weight; per weight class the count is a Matrix-Tree determinant on the contracted graph; multiply
Degree-constrained MST	NP-hard in general
Steiner tree (connect a subset)	NP-hard — Dreyfus-Wagner for small terminal sets
Minimum spanning arborescence	Chu-Liu/Edmonds
Dynamic MST (edges added/removed)	link-cut trees or offline

See also: Kruskal · DSU · Second-Best MST