---
title: Kruskal and Prim
module: Graphs
moduleNumber: 6
lessonNumber: 5
order: 605
summary: |
  The two minimum-spanning-tree algorithms you will actually implement.
  Kruskal grows a forest edge by edge, cheapest first, using a union-find
  structure to reject cycle-closing edges; Prim grows one tree outward from a
  root with a priority queue, exactly Dijkstra rekeyed by attachment cost. Both
  traced in full on a nine-town graph, with the edge cases, the bottleneck
  property, and where each one wins.
topics: [Minimum Spanning Trees, Union-Find]
sources:
  - book: CLRS
    ref: "Ch. 23 — Minimum Spanning Trees"
  - book: Skiena
    ref: "§6 — Weighted Graph Algorithms"
  - book: CLRS
    ref: "Ch. 21 — Data Structures for Disjoint Sets"
practice:
  - title: 'Path With Minimum Effort'
    slug: path-with-minimum-effort
    difficulty: Medium
  - title: 'Swim in Rising Water'
    slug: swim-in-rising-water
    difficulty: Hard
---

This builds on [Minimum Spanning Trees](/algorithms/graphs/minimum-spanning-trees), which set up the problem and proved the **cut property** (a light edge crossing a respecting cut is safe) and **cycle property** (a heaviest edge on a cycle is droppable). Everything below rests on those two certificates. The running example is the same nine-town graph from that lesson, whose unique MST has total weight $38$.

## Kruskal's algorithm

$\textsc{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? It reduces directly to the cut property.

> **Claim (Kruskal edges are safe).** Every edge Kruskal accepts is safe for the
> current forest $A$.

> **Proof.** 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. $\qed$

Each rejection is justified too: a rejected edge closes a cycle on which it is
a maximum-weight edge (everything already accepted is no heavier), so by the
cycle property some MST omits it.

The cycle test, "are $u$ and $v$ already in the same tree?", reduces to the
question $\text{comp}(u) \stackrel{?}{=} \text{comp}(v)$: does adding $(u, v)$
keep the graph acyclic? This is what the
[**disjoint-set** (union-find)](/algorithms/data-structures/union-find) data
structure answers efficiently.[^clrs-uf] It supports $\textsc{Make-Set}$, $\textsc{Find}$
($\text{comp}(x)$, which component is $x$ in?), and $\textsc{Union}$ (merge two
components).

```algorithm
caption: $\textsc{Kruskal}(G, c)$ — grow a forest, cheapest safe edge first
number: 3
$A \gets \emptyset$
foreach vertex $v \in V$ do
  call $\textsc{Make-Set}(v)$
sort the edges of $E$ into nondecreasing order by weight $c$
foreach edge $(u, v) \in E$ in sorted order do
  if $\textsc{Find}(u) \neq \textsc{Find}(v)$ then // stays acyclic
    $A \gets A \cup \set{(u, v)}$ // safe edge
    call $\textsc{Union}(u, v)$
return $A$
```

### A full trace, union-find state included

Running $\textsc{Kruskal}$ on the nine-town graph makes the accept/reject
rhythm visible. The thirteen edges in nondecreasing order (ties broken
alphabetically) are
$$
1, 2, 2, 4, 6, 7, 7, 7, 8, 9, 10, 11, 14.
$$
The table shows, for every edge scanned, the union-find test and the partition
of $V$ into components after the step:

| # | edge | $c_e$ | same component? | action | partition afterwards |
| --- | --- | --- | --- | --- | --- |
| 1 | $h$–$g$ | $1$ | no | accept | $\set{a}\,\set{b}\,\set{c}\,\set{d}\,\set{e}\,\set{f}\,\set{g,h}\,\set{i}$ |
| 2 | $c$–$i$ | $2$ | no | accept | $\set{a}\,\set{b}\,\set{c,i}\,\set{d}\,\set{e}\,\set{f}\,\set{g,h}$ |
| 3 | $g$–$f$ | $2$ | no | accept | $\set{a}\,\set{b}\,\set{c,i}\,\set{d}\,\set{e}\,\set{f,g,h}$ |
| 4 | $a$–$b$ | $4$ | no | accept | $\set{a,b}\,\set{c,i}\,\set{d}\,\set{e}\,\set{f,g,h}$ |
| 5 | $i$–$g$ | $6$ | no | accept | $\set{a,b}\,\set{c,f,g,h,i}\,\set{d}\,\set{e}$ |
| 6 | $b$–$c$ | $7$ | no | accept | $\set{a,b,c,f,g,h,i}\,\set{d}\,\set{e}$ |
| 7 | $c$–$d$ | $7$ | no | accept | $\set{a,b,c,d,f,g,h,i}\,\set{e}$ |
| 8 | $i$–$h$ | $7$ | **yes** | reject | unchanged |
| 9 | $a$–$h$ | $8$ | **yes** | reject | unchanged |
| 10 | $d$–$e$ | $9$ | no | accept | $\set{a,b,c,d,e,f,g,h,i}$ |
| 11 | $e$–$f$ | $10$ | **yes** | reject | unchanged |
| 12 | $b$–$i$ | $11$ | **yes** | reject | unchanged |
| 13 | $d$–$f$ | $14$ | **yes** | reject | unchanged |

Eight accepts, total weight $38$ — the MST from the opening figure. Once the
eighth edge lands (step 10) the forest is spanning and the loop could stop
early; steps 11–13 can only reject. Four snapshots of the growing forest:

$$
% caption: Kruskal's forest on the nine-town graph. Thick edges are accepted; dashed edges
%          are rejected because both endpoints already share a component.
\begin{tikzpicture}[font=\scriptsize,
  V/.style={circle, draw, minimum size=4.8mm, inner sep=0pt, font=\scriptsize},
  got/.style={line width=1.2pt, draw=acc},
  rej/.style={line width=1pt, draw=red, dashed}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{D1342B}
  % panel 1: after weights 1, 2, 2
  \begin{scope}[shift={(0,0)}]
    \node[V] (b1) at (0.9,1.1) {$b$};  \node[V] (c1) at (2.1,1.1) {$c$};
    \node[V] (d1) at (3.3,1.1) {$d$};  \node[V] (a1) at (0.25,0.35) {$a$};
    \node[V] (i1) at (1.85,0.35) {$i$}; \node[V] (e1) at (3.85,0.25) {$e$};
    \node[V] (h1) at (1.0,-0.45) {$h$}; \node[V] (g1) at (2.1,-0.55) {$g$};
    \node[V] (f1) at (3.2,-0.45) {$f$};
    \draw[black] (a1)--(b1); \draw[black] (b1)--(c1); \draw[black] (c1)--(d1);
    \draw[black] (b1)--(i1); \draw[black] (a1)--(h1); \draw[black] (i1)--(h1);
    \draw[black] (i1)--(g1); \draw[black] (d1)--(e1); \draw[black] (d1)--(f1);
    \draw[black] (e1)--(f1);
    \draw[got] (h1)--(g1); \draw[got] (c1)--(i1); \draw[got] (g1)--(f1);
    \node at (2.0,-1.35) {h-g 1, c-i 2, g-f 2};
  \end{scope}
  % panel 2: + 4, 6
  \begin{scope}[shift={(5.4,0)}]
    \node[V] (b2) at (0.9,1.1) {$b$};  \node[V] (c2) at (2.1,1.1) {$c$};
    \node[V] (d2) at (3.3,1.1) {$d$};  \node[V] (a2) at (0.25,0.35) {$a$};
    \node[V] (i2) at (1.85,0.35) {$i$}; \node[V] (e2) at (3.85,0.25) {$e$};
    \node[V] (h2) at (1.0,-0.45) {$h$}; \node[V] (g2) at (2.1,-0.55) {$g$};
    \node[V] (f2) at (3.2,-0.45) {$f$};
    \draw[black] (b2)--(c2); \draw[black] (c2)--(d2);
    \draw[black] (b2)--(i2); \draw[black] (a2)--(h2); \draw[black] (i2)--(h2);
    \draw[black] (d2)--(e2); \draw[black] (d2)--(f2); \draw[black] (e2)--(f2);
    \draw[got] (h2)--(g2); \draw[got] (c2)--(i2); \draw[got] (g2)--(f2);
    \draw[got] (a2)--(b2); \draw[got] (i2)--(g2);
    \node at (2.0,-1.35) {+ a-b 4, i-g 6};
  \end{scope}
  % panel 3: + 7, 7; rejects at 7 and 8
  \begin{scope}[shift={(0,-3.6)}]
    \node[V] (b3) at (0.9,1.1) {$b$};  \node[V] (c3) at (2.1,1.1) {$c$};
    \node[V] (d3) at (3.3,1.1) {$d$};  \node[V] (a3) at (0.25,0.35) {$a$};
    \node[V] (i3) at (1.85,0.35) {$i$}; \node[V] (e3) at (3.85,0.25) {$e$};
    \node[V] (h3) at (1.0,-0.45) {$h$}; \node[V] (g3) at (2.1,-0.55) {$g$};
    \node[V] (f3) at (3.2,-0.45) {$f$};
    \draw[black] (b3)--(i3); \draw[black] (d3)--(e3); \draw[black] (d3)--(f3);
    \draw[black] (e3)--(f3);
    \draw[got] (h3)--(g3); \draw[got] (c3)--(i3); \draw[got] (g3)--(f3);
    \draw[got] (a3)--(b3); \draw[got] (i3)--(g3); \draw[got] (b3)--(c3);
    \draw[got] (c3)--(d3);
    \draw[rej] (i3)--(h3); \draw[rej] (a3)--(h3);
    \node at (2.0,-1.35) {+ b-c 7, c-d 7};
  \end{scope}
  % panel 4: + 9, spanning
  \begin{scope}[shift={(5.4,-3.6)}]
    \node[V] (b4) at (0.9,1.1) {$b$};  \node[V] (c4) at (2.1,1.1) {$c$};
    \node[V] (d4) at (3.3,1.1) {$d$};  \node[V] (a4) at (0.25,0.35) {$a$};
    \node[V] (i4) at (1.85,0.35) {$i$}; \node[V] (e4) at (3.85,0.25) {$e$};
    \node[V] (h4) at (1.0,-0.45) {$h$}; \node[V] (g4) at (2.1,-0.55) {$g$};
    \node[V] (f4) at (3.2,-0.45) {$f$};
    \draw[got] (h4)--(g4); \draw[got] (c4)--(i4); \draw[got] (g4)--(f4);
    \draw[got] (a4)--(b4); \draw[got] (i4)--(g4); \draw[got] (b4)--(c4);
    \draw[got] (c4)--(d4); \draw[got] (d4)--(e4);
    \draw[rej] (e4)--(f4); \draw[rej] (b4)--(i4); \draw[rej] (d4)--(f4);
    \node at (2.0,-1.35) {+ d-e 9: total 38};
  \end{scope}
\end{tikzpicture}
$$

### Making it fast: union by size

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

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

Why this wins: whenever a vertex $x$ has its label $\text{comp}[x]$ rewritten,
it sat in the _smaller_ of the two merged components, so the component
containing $x$ **at least doubles** in size. After $k$ relabellings of $x$, its
component holds at least $2^k$ vertices; since no component exceeds $n$,
$2^k \le n$, i.e. $k \le \log_2 n$. Summing over vertices, the total work spent
updating $\text{comp}[\cdot]$ across _all_ unions is
$$
\sum_{x \in V} \#\text{relabellings of } x \;\le\; n \log_2 n = O(n \log n).
$$
The bound is loose in practice. In the trace above, the eight unions relabel
smaller sides of sizes $1, 1, 1, 1, 2, 2, 1, 1$: ten label rewrites total,
nowhere near $9 \log_2 9 \approx 29$.

**Running time.** The pieces are: sorting, $O(m \log m) = O(m \log n)$ since
$m \le n^2$ implies $\log m \le 2 \log n$; the $2m$ $\textsc{Find}$ calls at
$O(1)$ each; and $O(n \log n)$ total union work. Sorting dominates:
$$
T(n, m) = O(m \log n).
$$
The pointer-based union-find (union by rank plus path compression) does all
$m$ operations in $O(m\,\alpha(n))$, where $\alpha$ is the inverse Ackermann
function, at most $4$ for any input that fits in the physical universe. That
refinement only matters when sorting is _not_ the bottleneck: if the edges
arrive pre-sorted, or the weights are small integers that a counting or radix
sort handles in $O(m)$, Kruskal's total drops to $O(m\,\alpha(n))$, effectively
linear.

::impl{algo="kruskal"}

## Prim's algorithm

$\textsc{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.[^skiena-mst]

Safety is again the cut property.

> **Proof (Prim edges are safe).** Let $S$ be the vertices currently in the tree.
> The cut $(S, V \setminus S)$ respects $A$, and Prim deliberately picks the
> _lightest_ edge crossing it, a light edge, so the chosen edge is safe. $\qed$

This is **exactly [$\textsc{Dijkstra}$](/algorithms/graphs/shortest-paths) 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**](/algorithms/sorting/heaps-and-heapsort) keyed by
$\text{key}[v]$,
maintaining the invariant
$$
\forall v \in Q : \quad \text{key}[v] = \min_{x \notin Q}\; c_{xv}
\qquad\text{(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 $\textsc{Decrease-Key}$.

```algorithm
caption: $\textsc{Prim}(G, c, s)$ — grow one tree from an arbitrary start $s$
number: 4
foreach vertex $u \in V$ do
  $\text{key}[u] \gets \infty$
  $\pi[u] \gets \text{nil}$
$\text{key}[s] \gets 0$ // start tree at $s$
$Q \gets V$ // min-PQ keyed by $\text{key}$
$E' \gets \emptyset$
while $Q \neq \emptyset$ do
  $u \gets \textsc{Extract-Min}(Q)$ // cheapest to attach
  if $\pi[u] \neq \text{nil}$ then
    $E' \gets E' \cup \set{(\pi[u], u)}$ // commit safe edge
  foreach $v$ adjacent to $u$ with $v \in Q$ do
    if $c_{uv} < \text{key}[v]$ then
      $\pi[v] \gets u$ // $v$'s best link to tree
      $\text{key}[v] \gets c_{uv}$ // Decrease-Key
return $E'$
```

A single step in isolation: the tree $S = \set{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 \setminus S)$ respects the tree, and $\textsc{Extract-Min}$
returns the endpoint of the lightest crossing edge — here $c$–$i$ at weight
$2$ — which the cut property certifies as safe:

$$
% caption: A Prim snapshot: the grown tree $S$ (shaded, dashed box) and the frontier;
%          $\textsc{Extract-Min}$ pulls the lightest crossing edge ($c$–$i$, weight $2$).
\begin{tikzpicture}[>=Stealth, font=\small,
  T/.style={circle, draw, minimum size=8mm, fill=acc!25, font=\small},
  F/.style={circle, draw, minimum size=8mm, font=\small},
  wt/.style={font=\scriptsize, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{D1342B}
  \draw[dashed, black, fill=black!4] (-0.7,-0.7) rectangle (4.3,1.7);
  \node[font=\scriptsize, black] at (-0.25,1.4) {$S$};
  \node[T] (a) at (0,0.5) {$a$};
  \node[T] (b) at (1.7,1.0) {$b$};
  \node[T] (c) at (3.4,0.5) {$c$};
  \node[F] (i) at (3.2,-1.8) {$i$};
  \node[F] (d) at (6.0,1.0) {$d$};
  \node[F] (g) at (5.6,-1.8) {$g$};
  \draw[line width=1.4pt, acc] (a) -- node[wt, above left]{$4$} (b);
  \draw[line width=1.4pt, acc] (b) -- node[wt, above right]{$7$} (c);
  \draw[red, line width=1.3pt] (c) -- node[wt, left, fill=white, inner sep=1.5pt]{$2$} (i);
  \draw (c) -- node[wt, above]{$7$} (d);
  \draw (i) -- node[wt, below]{$6$} (g);
  \node[font=\scriptsize, red] at (1.4,-1.8) {min key$[i] = 2$};
  \node[font=\scriptsize, black, anchor=west] at (6.6,1.0) {key$[d] = 7$};
\end{tikzpicture}
$$

### A full trace, queue state included

Now the whole run, from root $a$ on the nine-town graph. Each row lists the
vertex extracted, the tree edge committed, the $\textsc{Decrease-Key}$ calls
its absorption triggers, and the queue contents afterwards (vertices with key
$\infty$ omitted):

| step | extracted | edge added | key updates ($\pi$ in parentheses) | queue after: $v$ : key |
| --- | --- | --- | --- | --- |
| 1 | $a$ (key $0$) | — | $b \gets 4$ ($a$), $h \gets 8$ ($a$) | $b{:}4,\ h{:}8$ |
| 2 | $b$ ($4$) | $a$–$b$ | $c \gets 7$ ($b$), $i \gets 11$ ($b$) | $c{:}7,\ h{:}8,\ i{:}11$ |
| 3 | $c$ ($7$) | $b$–$c$ | $i \gets 2$ ($c$), $d \gets 7$ ($c$) | $i{:}2,\ d{:}7,\ h{:}8$ |
| 4 | $i$ ($2$) | $c$–$i$ | $g \gets 6$ ($i$), $h \gets 7$ ($i$) | $g{:}6,\ d{:}7,\ h{:}7$ |
| 5 | $g$ ($6$) | $i$–$g$ | $h \gets 1$ ($g$), $f \gets 2$ ($g$) | $h{:}1,\ f{:}2,\ d{:}7$ |
| 6 | $h$ ($1$) | $g$–$h$ | — | $f{:}2,\ d{:}7$ |
| 7 | $f$ ($2$) | $g$–$f$ | $e \gets 10$ ($f$) | $d{:}7,\ e{:}10$ |
| 8 | $d$ ($7$) | $c$–$d$ | $e \gets 9$ ($d$) | $e{:}9$ |
| 9 | $e$ ($9$) | $d$–$e$ | — | empty |

Reading the table against the invariant: at every step the extracted key is
the weight of the lightest edge crossing the cut around the current tree, and
the committed edge $(\pi[u], u)$ is that light edge. $h$'s key falls
$8 \to 7 \to 1$ as the tree grows toward it, and $i$'s from $11$ to $2$ the
moment $c$ joins; a vertex's key only ever decreases. The same eight edges as
Kruskal arrive in a different order — Kruskal took $h$–$g$ first, Prim last
but one — because the two algorithms apply the cut property to different cuts.
Three snapshots of the growing tree, with each frontier vertex's cheapest
attachment drawn dashed:

$$
% caption: Prim from root $a$: tree vertices shaded, and each frontier vertex's best
%          attachment (its key) dashed. Panels show steps 1, 4, and 7 of the trace.
\begin{tikzpicture}[font=\scriptsize,
  T/.style={circle, draw, minimum size=4.8mm, inner sep=0pt, font=\scriptsize, fill=acc!20},
  F/.style={circle, draw, minimum size=4.8mm, inner sep=0pt, font=\scriptsize},
  tr/.style={line width=1.2pt, draw=acc},
  cand/.style={draw=acc, dashed, line width=0.9pt},
  wt/.style={font=\scriptsize, inner sep=1pt, fill=white}]
  \definecolor{acc}{HTML}{2348F2}
  % panel 1: S = {a}
  \begin{scope}[shift={(0,0)}]
    \node[F] (b1) at (0.9,1.1) {$b$};  \node[F] (c1) at (2.1,1.1) {$c$};
    \node[F] (d1) at (3.3,1.1) {$d$};  \node[T] (a1) at (0.25,0.35) {$a$};
    \node[F] (i1) at (1.85,0.35) {$i$}; \node[F] (e1) at (3.85,0.25) {$e$};
    \node[F] (h1) at (1.0,-0.45) {$h$}; \node[F] (g1) at (2.1,-0.55) {$g$};
    \node[F] (f1) at (3.2,-0.45) {$f$};
    \draw[black] (b1)--(c1); \draw[black] (c1)--(d1); \draw[black] (c1)--(i1);
    \draw[black] (b1)--(i1); \draw[black] (i1)--(h1); \draw[black] (i1)--(g1);
    \draw[black] (h1)--(g1); \draw[black] (g1)--(f1); \draw[black] (d1)--(e1);
    \draw[black] (d1)--(f1); \draw[black] (e1)--(f1);
    \draw[cand] (a1)--node[wt]{$4$}(b1); \draw[cand] (a1)--node[wt]{$8$}(h1);
    \node at (2.0,-1.35) {b 4, h 8};
  \end{scope}
  % panel 2: S = {a,b,c}, step 4 about to happen
  \begin{scope}[shift={(5.4,0)}]
    \node[T] (b2) at (0.9,1.1) {$b$};  \node[T] (c2) at (2.1,1.1) {$c$};
    \node[F] (d2) at (3.3,1.1) {$d$};  \node[T] (a2) at (0.25,0.35) {$a$};
    \node[F] (i2) at (1.85,0.35) {$i$}; \node[F] (e2) at (3.85,0.25) {$e$};
    \node[F] (h2) at (1.0,-0.45) {$h$}; \node[F] (g2) at (2.1,-0.55) {$g$};
    \node[F] (f2) at (3.2,-0.45) {$f$};
    \draw[black] (b2)--(i2); \draw[black] (i2)--(h2); \draw[black] (i2)--(g2);
    \draw[black] (h2)--(g2); \draw[black] (g2)--(f2); \draw[black] (d2)--(e2);
    \draw[black] (d2)--(f2); \draw[black] (e2)--(f2);
    \draw[tr] (a2)--(b2); \draw[tr] (b2)--(c2);
    \draw[cand] (c2)--node[wt, right]{$2$}(i2); \draw[cand] (c2)--node[wt]{$7$}(d2);
    \draw[cand] (a2)--node[wt]{$8$}(h2);
    \node at (2.0,-1.35) {i 2, d 7, h 8};
  \end{scope}
  % panel 3: S = {a,b,c,i,g,h}, step 7 about to happen
  \begin{scope}[shift={(2.7,-3.6)}]
    \node[T] (b3) at (0.9,1.1) {$b$};  \node[T] (c3) at (2.1,1.1) {$c$};
    \node[F] (d3) at (3.3,1.1) {$d$};  \node[T] (a3) at (0.25,0.35) {$a$};
    \node[T] (i3) at (1.85,0.35) {$i$}; \node[F] (e3) at (3.85,0.25) {$e$};
    \node[T] (h3) at (1.0,-0.45) {$h$}; \node[T] (g3) at (2.1,-0.55) {$g$};
    \node[F] (f3) at (3.2,-0.45) {$f$};
    \draw[black] (b3)--(i3); \draw[black] (i3)--(h3); \draw[black] (a3)--(h3);
    \draw[black] (d3)--(e3); \draw[black] (d3)--(f3); \draw[black] (e3)--(f3);
    \draw[tr] (a3)--(b3); \draw[tr] (b3)--(c3); \draw[tr] (c3)--(i3);
    \draw[tr] (i3)--(g3); \draw[tr] (g3)--(h3);
    \draw[cand] (g3)--node[wt]{$2$}(f3); \draw[cand] (c3)--node[wt]{$7$}(d3);
    \node at (2.0,-1.35) {f 2, d 7};
  \end{scope}
\end{tikzpicture}
$$

**Running time.** Prim performs $n$ $\textsc{Extract-Min}$ operations and up to
$m$ $\textsc{Decrease-Key}$ operations, so in general
$T(n, m) = O\parens{n\,(T_{\text{ins}} + T_{\text{ext}}) + m\,T_{\text{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**,
$\textsc{Decrease-Key}$ drops to $O(1)$ amortized while $\textsc{Extract-Min}$
stays $O(\log n)$, improving the total to
$$
T(n, m) = O(m + n \log n).
$$
When the graph is dense, $m = \Omega(n \log n)$, this is
$O(m)$, that is, **linear**, and
[asymptotically](/algorithms/foundations/asymptotic-analysis) the best known.
On very dense graphs there is an even simpler route to the same bound: skip
the heap, keep $\text{key}[\cdot]$ as a plain array, and find each minimum by
scanning it. That is $n$ scans at $O(n)$ plus $O(1)$ per key update, for
$O(n^2 + m) = O(n^2)$ total — on a complete graph ($m = \Theta(n^2)$) this
plain-array Prim is linear in the input size and beats the heap version's
$O(n^2 \log n)$.

::impl{algo="prim"}

## Edge cases and pitfalls

**Equal weights.** Nothing in the cut-property proof requires distinct weights
(it only uses $c_e \le c_g$), so Kruskal and Prim are correct as stated under
ties; the MST just may not be unique, and different tie-breaks yield different,
equally cheap trees. The one algorithm that needs care is Borůvka's, where an
inconsistent tie-break can create a cycle within a single round — hence the
fixed total order in the remark above. If you need _the_ MST to be well
defined (say, for hashing or comparison), perturb ties by edge index: order by
$(c_e, \text{index}(e))$ lexicographically.

**Negative weights are harmless.** Every spanning tree has exactly $n - 1$
edges, so adding a constant $K$ to every weight adds exactly $(n-1)K$ to every
spanning tree's cost and preserves their relative order. MST algorithms only
ever _compare_ weights. Contrast Dijkstra, where shifting weights breaks
correctness precisely because paths have different edge counts.

**An MST is not a shortest-path tree.** The MST minimizes one global sum; it
guarantees nothing about the path between any particular pair. In the nine-town
graph the MST joins $a$ to $h$ through $a$–$b$–$c$–$i$–$g$–$h$ at cost
$4 + 7 + 2 + 6 + 1 = 20$, while the direct edge $a$–$h$ costs $8$. Building the
MST and then reading distances off it is a classic error.

**What an MST _does_ guarantee about paths.** It minimizes the _bottleneck_:

> **Theorem (Bottleneck property).** Every MST minimizes, over all spanning
> trees, the weight of its maximum edge.

> **Proof.** Let $T$ be an MST with heaviest edge $f$, and delete $f$ from $T$
> to get the cut $(S, V \setminus S)$. If some crossing edge $e'$ had
> $c_{e'} < c_f$, then $T - f + e'$ would be a cheaper spanning tree, so $f$ is
> a _light_ edge on this cut. Any spanning tree must use some crossing edge and
> therefore pays at least $c_f$ on its maximum. $\qed$

This is why MSTs answer minimax questions: the path between $u$ and $v$ inside
an MST minimizes the maximum edge weight over _all_ $u$–$v$ paths. Two of the
practice problems (Path With Minimum Effort, Swim in Rising Water) amount to
this bottleneck property in disguise.

**Heaviest edge, again.** The cycle property removes the heaviest edge _on
each cycle_, not the heaviest edge of the graph; a heavy bridge survives every
MST (the figure in the cycle-property section). Symmetrically, a **maximum**
spanning tree needs no new theory: negate all weights, or flip the
comparisons.

**Disconnected input.** If $G$ is not connected no spanning tree exists.
Kruskal degrades gracefully: it returns the **minimum spanning forest** (an MST
of each component) with no code change, since it never needed connectivity.
Prim must be restarted once per component, as its single tree can never cross
between them.

## 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\,\alpha(n))$ work after sort | $O(m + n \log n)$ (Fib. heap) |
| Best when | parallel / distributed | edges already sorted; sparse | dense; adjacency-rich data |

The tie-breakers in practice: Kruskal wins on sparse graphs and whenever the
edges come pre-sorted or sort in linear time (integer weights), since what
remains is near-linear union-find work; it also handles edge lists with no
adjacency structure and disconnected inputs directly. Prim wins on dense
graphs, especially with the plain-array variant at $O(n^2)$, and on implicitly
dense inputs like "connect these points in the plane" where materializing and
sorting all $\Theta(n^2)$ candidate edges just to feed Kruskal is the expensive
part. Borůvka wins when the work must be split across machines or threads,
and its rounds compose with the other two: run a few Borůvka rounds to shrink
the graph, then finish with Prim or Kruskal — the fastest practical schemes are
hybrids of exactly this shape.

All three are correct for the _same_ reason, the cut property, and all three are
greedy algorithms whose greediness is _provably_ optimal — rare for greedy
strategies.


## What MSTs are used for

Beyond network design, the MST is a building block in data analysis and approximation.

**Single-linkage clustering.** Run Kruskal but stop early, after $n - k$ edges: the $k$ remaining components are the clusters that **single-linkage agglomerative clustering** would form.[^clustering] Merging the two closest clusters is precisely accepting the next-cheapest Kruskal edge, so the whole MST _is_ the clustering dendrogram, and cutting it at a chosen height gives any number of clusters for free. Deleting the $k-1$ heaviest MST edges partitions the points into the $k$ groups that maximize the smallest inter-cluster gap — the cut and bottleneck properties at work on real data.

**Approximating hard tours.** The metric [travelling-salesman problem](/algorithms/intractability/np-completeness) is NP-hard, but the MST gives a fast $2$-approximation: build the MST, walk it in a depth-first order (a full traversal crosses each edge twice, costing $2 \cdot \text{MST}$), and shortcut past repeats. Since the optimal tour minus one edge is a spanning tree, $\text{MST} \le \text{OPT}$, so the shortcut tour costs at most $2\,\text{OPT}$. Christofides' refinement adds a minimum matching on the odd-degree vertices to reach a $1.5$-approximation — still the classic guarantee for metric TSP, and the MST is its foundation.

$$
% caption: MST as a TSP approximation. Left: the MST of five cities. Right: a DFS walk of
%          the MST (each edge twice) shortcut past repeated visits yields a tour of cost at
%          most twice the MST, hence at most twice the optimal tour.
\begin{tikzpicture}[font=\scriptsize,
  V/.style={circle, draw, minimum size=5mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % left: MST
  \node[V] (a) at (0,1.4) {$1$}; \node[V] (b) at (1.4,1.7) {$2$};
  \node[V] (c) at (2.0,0.4) {$3$}; \node[V] (d) at (0.6,0) {$4$};
  \node[V] (e) at (2.6,1.4) {$5$};
  \draw[acc, line width=1.3pt] (a)--(b); \draw[acc, line width=1.3pt] (a)--(d);
  \draw[acc, line width=1.3pt] (b)--(c); \draw[acc, line width=1.3pt] (b)--(e);
  \node[font=\scriptsize] at (1.3,-0.8) {MST};
  % right: shortcut tour
  \begin{scope}[shift={(5,0)}]
    \node[V] (a2) at (0,1.4) {$1$}; \node[V] (b2) at (1.4,1.7) {$2$};
    \node[V] (c2) at (2.0,0.4) {$3$}; \node[V] (d2) at (0.6,0) {$4$};
    \node[V] (e2) at (2.6,1.4) {$5$};
    \draw[->, acc, line width=1.1pt] (a2) to[bend left=8] (b2);
    \draw[->, acc, line width=1.1pt] (b2) to[bend left=8] (e2);
    \draw[->, acc, line width=1.1pt] (e2) to[bend left=10] (c2);
    \draw[->, acc, line width=1.1pt] (c2) to[bend left=8] (d2);
    \draw[->, acc, line width=1.1pt] (d2) to[bend left=20] (a2);
    \node[font=\scriptsize] at (1.3,-0.8) {shortcut tour: cost at most 2 MST};
  \end{scope}
\end{tikzpicture}
$$

The list runs long: MSTs underlie network design and broadcast trees, image segmentation (Felzenszwalb-Huttenlocher runs single-linkage on a pixel grid), the taut-string structure of point clouds, and the "bottleneck" routing problems from the practice set. Whenever a problem asks to connect everything cheaply, to find the widest-gap partition, or to approximate a metric optimization, the MST is the standard starting point.

## 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 **generic method** adds one **safe** edge at a time, maintaining the
  invariant that the growing edge set sits inside some MST; after $n - 1$
  additions the invariant forces equality.
- The **cut property** is the inclusion certificate: 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.
- The **cycle property** is the exclusion certificate: a heaviest edge on any
  cycle can be dropped, and a _strictly_ heaviest one is in no MST. It applies
  only to cycle edges; bridges are in every spanning tree. Distinct weights
  make the MST unique.
- $\textsc{Borůvka}$ adds every component's cheapest exit edge each round; the
  component count at least halves, giving $O(\log n)$ rounds and $O(m \log n)$
  total, with naturally parallel rounds.
- $\textsc{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_2 n$ times.
- $\textsc{Prim}$ is $\textsc{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, $O(n^2)$ with a plain array — linear on dense graphs either way.
- MSTs tolerate negative weights and ties, minimize the **bottleneck** edge on
  every path, and are _not_ shortest-path trees.


[^skiena-mst]: **Skiena**, §6 — Weighted Graph Algorithms — Prim's algorithm growing one tree via a priority queue.
[^clrs-uf]: **CLRS**, Ch. 21 — Data Structures for Disjoint Sets — union by size/rank and path compression, with the $O(m\,\alpha(n))$ bound.
[^clustering]: **Skiena**, §6 — Weighted Graph Algorithms — single-linkage clustering as the minimum spanning tree cut at a chosen number of components.