---
title: "Minimum Spanning Tree"
summary: Kruskal, Prim, and Borůvka from one lemma; the cut property, the exchange argument, and what each algorithm is actually for.
difficulty: core
tags: [mst, greedy, dsu, heap]
time: m log m
space: n + m
prereq: [foundations/types, structures/dsu]
see: [flow/mcmf, structures/segment-tree]
---

## The cut property

:::definition label="MST"
For a connected weighted undirected graph, a **minimum spanning tree** is a spanning tree $T$ minimising $\sum_{e \in T} w(e)$. Write $\operatorname{MST}(G)$ for its weight. With equal weights it is just "any spanning tree"; with $\{0,1\}$ weights it is "the fewest expensive edges".
:::

:::theorem title="The cut property (the only lemma you need)"
Let $\varnothing \ne S \subsetneq 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.
:::

:::proof
Take any MST $T$. If $e \in 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) \ge w(e)$. Then $T' = T - f + e$ is a spanning tree (removing $f$ breaks the only cycle) with $\operatorname{wt}(T') \le \operatorname{wt}(T)$, so $T'$ is minimum and contains $e$. If $w(f) > w(e)$, $T$ was not minimal — contradiction, which proves the uniqueness claim. ∎
:::

:::note title="Every MST algorithm is this lemma, scheduled differently"
- **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 $(\bigcup A, V \setminus \bigcup 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: $2^i$ 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

```cpp kruskal.cpp
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

:::props title="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(n^2)$ | adjacency **matrix** | dense graphs, $m = \Theta(n^2)$ — 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

:::theorem title="Two properties worth memorising"
- **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 @advanced-tree/hld or $O(n^2)$ 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 $\operatorname{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$").
:::

:::demo id="mst" caption="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."
:::

:::example title="Kruskal's real superpower: the union tree"
While running Kruskal, when edge $e$ merges components $A$ and $B$, create a new node $x$ with children $\operatorname{root}(A), \operatorname{root}(B)$ and weight $w(e)$, and make $x$ the merged component's representative (DSU with explicit roots, @structures/dsu). The result is the **Kruskal reconstruction tree**: $n + (n-1)$ nodes, and $\operatorname{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 $\le W$" is then one LCA (and "the set of vertices reachable from $u$ with edges $\le W$" is the subtree of the highest ancestor of $u$ of weight $\le 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

:::warning title="Directed MST is a different 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 @flow/maxflow for how orientation constraints are handled by flow instead.
:::

:::problems
- [[CSES 1666]] Building Roads | https://cses.fi/problemset/task/1666 | easy | the unweighted case: MST weight = components - 1
- [[CF 160D]] Edges in MST | https://codeforces.com/problemset/problem/160/D | core | classify every edge: in some / every / no MST
:::