Minimum Spanning Trees

Suppose you must lay cable to connect a set of towns, and every possible connection has a known cost. You want all the towns linked — any town reachable from any other — while spending as little as possible. Laying a redundant link would only waste money, so the cheapest solution can contain no cycle: it is a tree that spans every town. Finding the cheapest such tree is the minimum spanning tree problem, and it is the first place in this course where a greedy strategy is provably optimal.

The problem

Stated precisely, in the shape the rest of this lesson will use:

Here a tree means a connected, acyclic graph, not to be confused with a rooted or rooted-and-ordered tree; an MST has no distinguished root. A spanning tree on $n = ∣ V ∣$ vertices always has exactly $n - 1$ edges: enough to connect everything, one fewer than would create a cycle.

It is worth recalling why tree is exactly the right object. For a graph $G = (V, E)$ the following are equivalent, and any one of them could serve as the definition.

Below, a weighted graph (left) and one of its minimum spanning trees (the thick colored edges):

A weighted graph with one minimum spanning tree shown in thick edges.

The thick tree spans all nine towns with total weight $1 + 2 + 2 + 4 + 6 + 7 + 7 + 9 = 38$ ; no spanning tree is cheaper.

The cut property

All three algorithms below are instances of a single greedy template: maintain a set $A$ of edges that is always a subset of some MST, and at each step add one more safe edge, meaning an edge that can be added to $A$ while keeping $A \subseteq$ (some MST). The entire theory of MSTs reduces to recognizing safe edges, and one lemma does that for us.¹

First, the vocabulary. A cut $(S, V ∖ S)$ is a partition of the vertices into two groups. An edge crosses the cut if its endpoints lie on opposite sides. A cut respects an edge set $A$ if no edge of $A$ crosses it. An edge crossing the cut is light (or cheapest) if it has the minimum weight of all crossing edges.

A cut splitting vertices into

S

and its complement, with the light crossing edge highlighted.

Proof (an exchange argument — done carefully). Let $T^{*}$ be an MST containing $A$ , and suppose, for contradiction, that no MST contains $e$ . Since $T^{*}$ is connected, there is at least one edge of $T^{*}$ crossing the cut $(S, V ∖ S)$ .

It is tempting to grab any such crossing edge $f \in T^{*}$ , swap it for $e$ , and argue $T^{*} - f + e$ is a cheaper tree. This is a mistake: removing an arbitrary crossing edge $f$ need not reconnect into a tree once we add $e$ ; the result can be disconnected or contain a cycle. We must remove the right edge.

So instead: adding $e$ to $T^{*}$ creates a unique cycle, and because $e$ crosses the cut, that cycle must cross back at some edge $g \in T^{*}$ , with $g$ also crossing $(S, V ∖ S)$ . Because the cut respects $A$ , this $g \in / A$ . Form

T^{'} = T^{*} - {g} + {e} .

Deleting $g$ breaks the unique cycle, so $T^{'}$ is again a spanning tree, and it still contains $A \cup {e}$ . Since $e$ is the light crossing edge, $c_{e} \leq c_{g}$ , hence

cost (T^{'}) = cost (T^{*}) - c_{g} + c_{e} \leq cost (T^{*}) .

But $T^{*}$ was minimum, so equality holds: $T^{'}$ is also an MST, and it contains $e$ . Contradiction. Therefore some MST contains $A \cup {e}$ , i.e. $e$ is safe. $■$

The exchange argument: adding edge

e

creates a cycle whose crossing edge

g

is swapped out.

The cut property is the engine. Every correct MST algorithm, whether Borůvka's, Prim's, or Kruskal's, is just a strategy for choosing which cut to apply it to, and all three only ever add edges that obey the cut rule.

Borůvka's algorithm

The oldest MST algorithm (Otakar Borůvka, 1926) is also the most directly cut-rule driven, and it parallelises well.² The idea: every component, in every round, simultaneously reaches out along its own cheapest outgoing edge.

Maintain a forest $A$ , initially the $n$ isolated vertices. In each round, each current component $C$ looks at the cut $(C, V ∖ C)$ , which respects $A$ , and selects its lightest crossing edge. By the cut property every such edge is safe, so we add them all at once and merge the components they join. Because every component at least halves in count each round (each one merges with at least one neighbor), the number of components drops by a factor $\geq 2$ per round, so only $O (log V)$ rounds are needed.

Algorithm 1:

\textsc{Borůvka}(G, c)

— every component grabs its cheapest exit edge

1
$A \gets \emptyset$
$n$ singleton components
2
while $A$ has more than one component do
3
foreach component $C$ of $(V, A)$ do
4
$e_C \gets$ the lightest edge crossing $(C,\, V \setminus C)$
safe by cut rule
5
foreach distinct edge $e_C$ chosen do
6
$A \gets A \cup \set{e_C}$
add all exit edges at once
7
return $A$

Running time. Each round scans all edges to find component-minimum exits in $O (E)$ time and there are $O (log V)$ rounds, so $Bor \overset{u}{˚} vka$ runs in $O (E log V)$ , the same headline bound as Prim and Kruskal, but with the useful property that the per-round work is fully parallel.

One round on six isolated vertices shows the parallel grab. Each singleton (a component of one) points an arrow along its own cheapest incident edge; the chosen edges, taken together, merge the six components down to two in a single sweep:

One Borůvka round: every component (here singletons) selects its cheapest exit edge (red arrows). The five chosen edges merge six components into two.

Kruskal's algorithm

$Kruskal$ 's strategy is global and edge-centric: consider the edges in order of increasing weight, and add each one unless it would form a cycle. The set $A$ is a forest (an acyclic graph) that gradually coalesces into a single tree once $G$ is fully connected.

Why is each added edge safe? When Kruskal accepts the cheapest remaining edge $(u, v)$ , it connects two different trees of the current forest. Take $S$ to be the vertices of $u$ 's tree. This cut respects $A$ (no forest edge crosses out of a tree), and $(u, v)$ is the lightest edge crossing it; any lighter crossing edge would have been considered earlier and would have joined the trees already. By the cut property, $(u, v)$ is safe.

The cycle test, are $u$ and $v$ already in the same tree?, is exactly the question $comp (u) = ? comp (v)$ : does adding $(u, v)$ keep the graph acyclic? This is what the disjoint-set (union-find) data structure answers efficiently. It supports $Make-Set$ , $Find$ ( $comp (x)$ , which component is $x$ in?), and $Union$ (merge two components).

Algorithm 2:

\textsc{Kruskal}(G, c)

— grow a forest, cheapest safe edge first

1
$A \gets \emptyset$
2
foreach vertex $v \in V$ do
3
call $\textsc{Make-Set}(v)$
4
sort the edges of $E$ into nondecreasing order by weight $c$
5
foreach edge $(u, v) \in E$ in sorted order do
6
if $\textsc{Find}(u) \neq \textsc{Find}(v)$ then
stays acyclic
7
$A \gets A \cup \set{(u, v)}$
safe edge
8
call $\textsc{Union}(u, v)$
9
return $A$

Running $Kruskal$ on the nine-town graph above makes the accept/reject rhythm visible. We scan the thirteen edges in nondecreasing weight; the first eight that join distinct trees are accepted, and the five that would close a cycle are skipped. The eight accepted edges are exactly the MST of weight $38$ :

Kruskal's edge-by-edge trace on the nine-town graph: accept an edge unless both ends already share a tree. Eight accepts total

38

Making it fast: union by size

The simplest implementation keeps an array $comp [1 \dots n]$ where $comp [v]$ names $v$ 's current component. Then $Find$ is $O (1)$ , but a naive $Union$ that relabels one whole side costs $O (n)$ in the worst case. The fix is the classic union-by-size argument:

Alongside $comp [\cdot]$ , keep $members [c]$ , a linked list of the vertices currently in component $c$ , so we can enumerate a component cheaply.
On $Union (u, v)$ , relabel the smaller component: choose the side with $∣ comp_{u} ∣ \leq ∣ comp_{v} ∣$ and rewrite $comp [x]$ for the vertices $x$ in that smaller side.

Why this wins: whenever a vertex $x$ has its label $comp [x]$ rewritten, it sat in the smaller of the two merged components, so the component containing $x$ at least doubles in size. A vertex can be doubled at most $log_{2} n$ times before it is in a component of all $n$ vertices. Hence each vertex is relabelled $O (log n)$ times across the whole run, and the total work spent updating $comp [\cdot]$ over all unions is $O (n log n)$ .

Running time. Sorting the edges dominates: $O (m log m) = O (m log n)$ since $m \leq n^{2}$ . The union-find work adds only $O (n log n)$ with union by size (and is effectively linear, $O (m α (n))$ , with the inverse-Ackermann tricks of union-by-rank plus path compression). So overall $Kruskal$ runs in

T (n, m) = O (m log n) .

Prim's algorithm

$Prim$ 's strategy is local and vertex-centric: grow a single tree outward from an arbitrary root, repeatedly attaching the cheapest edge that links a tree vertex to a non-tree vertex. Here the set $A$ is always one connected tree.³

Safety is again the cut property. Let $S$ be the vertices currently in the tree. The cut $(S, V ∖ S)$ respects $A$ , and Prim deliberately picks the lightest edge crossing it, a light edge, so the chosen edge is safe.

This is exactly $Dijkstra$ with the relaxation rule changed. Where Dijkstra keys a frontier vertex by $d [x] + c_{xv}$ (distance from the source), Prim keys it by $c_{xv}$ alone (cost to attach to the finished set). Prim keeps every non-tree vertex $v$ in a min-priority queue keyed by $key [v]$ , maintaining the invariant

\forall v \in Q : key [v] = min_{x \in / Q} c_{xv} (the cheapest way to connect v to a finished vertex).

Extracting the minimum yields the next vertex to absorb; absorbing it may make its neighbors cheaper to reach, so we relax their keys with $Decrease-Key$ .

Algorithm 3:

\textsc{Prim}(G, c, s)

— grow one tree from an arbitrary start

s

1
foreach vertex $u \in V$ do
2
$\text{key}[u] \gets \infty$
3
$\pi[u] \gets \text{nil}$
4
$\text{key}[s] \gets 0$
start tree at $s$
5
$Q \gets V$
min-PQ keyed by $\text{key}$
6
$E' \gets \emptyset$
7
while $Q \neq \emptyset$ do
8
$u \gets \textsc{Extract-Min}(Q)$
cheapest to attach
9
if $\pi[u] \neq \text{nil}$ then
10
$E' \gets E' \cup \set{(\pi[u], u)}$
commit safe edge
11
foreach $v$ adjacent to $u$ with $v \in Q$ do
12
if $c_{uv} < \text{key}[v]$ then
13
$\pi[v] \gets u$
$v$ 's best link to tree
14
$\text{key}[v] \gets c_{uv}$
Decrease-Key
15
return $E'$

A single Prim step looks like this. The tree $S = {a, b, c}$ has been grown from root $a$ ; every frontier vertex carries a key equal to its cheapest edge into $S$ . The cut $(S, V ∖ S)$ respects the tree, and $Extract-Min$ returns the endpoint of the lightest crossing edge — here $c - i$ at weight $2$ — which the cut property certifies as safe:

A Prim snapshot: the grown tree

S

(shaded, dashed box) and the frontier;

Extract-Min

pulls the lightest crossing edge (

c - i

, weight

2

Running time. Prim performs $n$ $Extract-Min$ operations and up to $m$ $Decrease-Key$ operations, so in general $T (n, m) = O (n (T_{ins} + T_{ext}) + m T_{dec})$ . With a binary heap all three operations cost $O (log n)$ , giving $O (m log n)$ , the same as Kruskal. With a Fibonacci heap, $Decrease-Key$ drops to $O (1)$ amortized while $Extract-Min$ stays $O (log n)$ , improving the total to

T (n, m) = O (m + n log n) .

Notice that when the graph is dense, $m = Ω (n log n)$ , this is $O (m)$ , that is, linear, and asymptotically the best known.

Which to use?

Throughout, $n = ∣ V ∣$ and $m = ∣ E ∣$ .

	Borůvka	Kruskal	Prim
Grows	every component at once	a forest, globally	a single tree, from a root
Core structure	component scan / union-find	union-find (union by size)	priority queue
Headline time	$O (m log n)$	$O (m log n)$	$O (m log n)$
Best variant	parallel rounds	$O (m α (n))$ work after sort	$O (m + n log n)$ (Fib. heap)
Shines when	parallel / distributed	edges already sorted; sparse	dense; adjacency-rich data

All three are correct for the same reason, the cut property, and all three are greedy algorithms whose greediness is provably optimal, a rarity worth savoring. If edge weights are not distinct the MST may not be unique, but every choice these algorithms make is still safe, so they always return a minimum spanning tree. (The fastest known practical approaches combine Borůvka's rounds with Prim/Kruskal to shave the bound further.)

Takeaways

A minimum spanning tree connects all $n$ vertices of a connected weighted graph with exactly $n - 1$ edges of least total weight; tree means connected and acyclic, no root.
The cut property (cut rule) is the one lemma behind every MST algorithm: a light edge crossing a cut that respects the current edge set is always safe. The exchange argument must swap out the edge $g$ on the cycle created by adding $e$ ; swapping an arbitrary crossing edge is a tempting mistake.
$Bor \overset{u}{˚} vka$ adds every component's cheapest exit edge each round; halving the component count gives $O (log n)$ rounds and $O (m log n)$ total, with naturally parallel rounds.
$Kruskal$ adds edges cheapest-first, skipping cycle-forming ones, using union-find; sorting dominates at $O (m log n)$ , and union by size keeps the relabelling work to $O (n log n)$ because each vertex's component can double only $log n$ times.
$Prim$ is $Dijkstra$ rekeyed by attachment cost: grow one tree from a start vertex, attaching the lightest crossing edge via a priority queue; $O (m log n)$ with a binary heap, $O (m + n log n)$ with a Fibonacci heap, linear on dense graphs.
Greedy is optimal here, a clean, provable success of the greedy paradigm.

CLRS, Ch. 23 — Minimum Spanning Trees — the cut property identifying a safe edge for the greedy MST template. ↩
Erickson, Ch. 8 — Minimum Spanning Trees — Borůvka's component-merging rounds in $O (log V)$ phases. ↩
Skiena, §6 — Weighted Graph Algorithms — Prim's algorithm growing one tree via a priority queue. ↩