Prim's Algorithm

A spanning tree of a connected, undirected graph $G = (V, E)$ is a subset of $|V| - 1$ edges that connects all vertices without forming a cycle. A minimum spanning tree is a spanning tree whose total edge weight is smallest among all spanning trees. Prim's algorithm computes an MST by maintaining a single growing tree $T$, initially just one arbitrary vertex, and repeatedly adding the lightest edge that connects a vertex already in $T$ to a vertex outside $T$. The key structural object is the cut: a partition of $V$ into two nonempty sets $S$ and $V \setminus S$. Any edge with one endpoint in each side is said to cross the cut. The cut property states that if an edge is the unique minimum-weight edge crossing some cut, then it belongs to every MST of the graph (or at least one, if ties are broken consistently). Prim's algorithm is essentially a mechanized proof of the cut property: at every iteration, the current tree $T$ defines the cut $(T, V \setminus T)$, and the algorithm greedily selects the minimum-weight edge across that exact cut. To find that minimum edge efficiently at every step, the algorithm maintains, for every vertex $v$ not yet in the tree, a running value `key[v]` equal to the weight of the cheapest edge seen so far connecting $v$ to the tree, along with a pointer `parent[v]` recording which tree vertex offers that edge. A min-priority queue keyed on `key[v]` lets the algorithm repeatedly extract the frontier vertex with the smallest key in logarithmic time. This is precisely the same bookkeeping used in Dijkstra's Algorithm — the difference is that Dijkstra's key is the cumulative distance from the source, while Prim's key is the weight of a single connecting edge, ignoring everything already traveled.

The algorithm proceeds in three phases: initialization, repeated extraction of the cheapest frontier vertex, and relaxation of its neighbors. 1. Initialize. Pick an arbitrary start vertex $r$. Set `key[r] = 0` and `key[v] = ∞` for every other vertex. Set `parent[v] = NIL` for all $v$. Insert all vertices into a min-priority queue keyed by `key`. 2. Extract. Repeatedly remove the vertex $u$ with the smallest `key` value from the queue. This vertex is now considered "in the tree." If `parent[u] ≠ NIL`, the edge `(parent[u], u)` is added to the MST. 3. Relax. For every neighbor $v$ of $u$ still in the queue, if the weight $w(u, v)$ is smaller than the current `key[v]`, update `key[v] = w(u, v)` and `parent[v] = u`, and adjust $v$'s position in the priority queue (a `decrease-key` operation). The process terminates when the queue is empty, at which point every vertex has been pulled in exactly once and the `parent` pointers describe a spanning tree of minimum total weight. ```text PRIM-MST(G, w, r): for each vertex v in G.V: key[v] ← ∞ parent[v] ← NIL in_tree[v] ← false key[r] ← 0 Q ← min-priority queue containing all vertices, keyed by key[] while Q is not empty: u ← EXTRACT-MIN(Q) # vertex with smallest key not yet in tree in_tree[u] ← true if parent[u] ≠ NIL: add edge (parent[u], u) to MST result for each (u, v) in G.adj[u]: if in_tree[v] = false and w(u, v) < key[v]: key[v] ← w(u, v) parent[v] ← u DECREASE-KEY(Q, v, key[v]) return set of edges {(parent[v], v) : v ≠ r} ``` Two points deserve emphasis. First, `key[v]` never represents a path length or accumulated cost — it is always the weight of a single edge, refreshed whenever a cheaper direct connection to the tree is discovered. Second, the algorithm never needs to check for cycles explicitly (unlike Kruskal's, which needs union-find): because `EXTRACT-MIN` only ever pulls a vertex not already in the tree, every added edge necessarily connects a new vertex, so a cycle can never form.

Correctness. The proof is a direct instantiation of the cut property, proved by induction on the number of edges added. Invariant: After each iteration, the edges chosen so far form a subset of some minimum spanning tree of $G$. Base case: With zero edges chosen, the empty set is trivially a subset of any MST. Inductive step: Suppose the invariant holds after $k$ edges have been added, forming tree $T$ on vertex set $S$. Consider the cut $(S, V \setminus S)$. The algorithm's next chosen edge $e = (u, v)$, with $u \in S$ and $v \notin S$, is by construction the minimum-weight edge crossing this cut — this is exactly what `key[]` and `EXTRACT-MIN` guarantee, since every vertex outside $S$ has its `key` value set to the weight of the lightest edge connecting it to $S$, and the extracted vertex has the smallest such key among all frontier vertices. By the cut property, this minimum-weight crossing edge belongs to some MST consistent with the edges already chosen. Hence the invariant is preserved. Termination: The loop runs exactly $|V|$ times (once per `EXTRACT-MIN`), adding $|V| - 1$ edges in total (the first extraction adds no edge, since `parent[r] = NIL`). When the queue empties, $S = V$, and by the invariant the collected edges form a spanning tree that is a subset of an MST on all of $V$ — but any spanning tree with $|V|-1$ edges that is a subset of an MST must equal that MST, since both have the same edge count. Hence the output is a genuine minimum spanning tree. Note that this argument silently assumes $G$ is connected; if $G$ is disconnected, Prim's algorithm as stated only discovers a minimum spanning tree of the connected component containing $r$, and some `key` values remain $\infty$ forever.

Time complexity. The dominant costs are `EXTRACT-MIN` (called $|V|$ times) and `DECREASE-KEY` (called at most once per edge, so $O(E)$ times).

• Binary heap: `EXTRACT-MIN` costs $O(\log V)$, `DECREASE-KEY` costs $O(\log V)$. Total:

since the graph is connected, so $E \ge V - 1$.

• Fibonacci heap: `EXTRACT-MIN` costs $O(\log V)$ amortized, but `DECREASE-KEY` costs $O(1)$ amortized. Total:

This is the asymptotically fastest known comparison-based bound for general graphs and matches Dijkstra's complexity with the same data structure.

• Adjacency matrix without a heap: scanning for the minimum key directly among $O(V)$ candidates each round costs $O(V^2)$ overall, which beats $O(E \log V)$ when the graph is dense ($E$ close to $V^2$), since $\log V$ overhead is avoided entirely.

Space complexity is $O(V + E)$: the adjacency list (or matrix), the `key`/`parent`/`in_tree` arrays of size $V$, and the priority queue holding up to $V$ entries.

Tradeoffs. Prim's algorithm requires no global edge sort and no union-find, but every `DECREASE-KEY` touches the priority queue, so a naive implementation without a proper decrease-key-capable heap (e.g., a plain binary heap with lazy deletion instead) degrades performance. On sparse graphs, Kruskal's Algorithm with a good union-find structure ($O(E \log E)$, dominated by the initial sort) is often simpler to reason about and just as fast in practice. Prim's real advantage emerges on dense graphs and in settings — such as incremental network design — where growing a single connected structure is more natural than merging fragments.

Consider six routers $A, B, C, D, E, F$ with the following candidate cable costs (undirected):

Start Prim's algorithm at vertex $A$.

Resulting MST edges: A–C (1), B–C (2), B–D (5), D–E (2), E–F (3). Total weight = 13. Trace check: at Step 2 the algorithm rejects the tempting-looking edge A–B (weight 4) in favor of A–C (weight 1) — the priority queue never even considers A–B until B's key is set, and by the time B is extracted, its key has already been lowered from 4 to 2 via C, correctly reflecting that reaching B through C is cheaper than a direct A–B cable. This illustrates why `key[]` must be continuously relaxed rather than fixed at initialization: the cheapest known connection to the tree can improve as the tree grows, exactly mirroring the relaxation step in Dijkstra's algorithm, but comparing single edges rather than path sums.

Prim's algorithm is named for Robert C. Prim, who published it in 1957 while working at Bell Labs, though the same greedy tree-growing idea had been discovered independently and earlier by the Czech mathematician Vojtěch Jarník in 1930, making the algorithm's true origins a striking case of parallel discovery separated by nearly three decades. Edsger W. Dijkstra rediscovered and popularized essentially the same algorithm in 1959, in the same paper that introduced his shortest-path algorithm — a historical fact that explains why the two algorithms share an almost identical priority-queue skeleton.

Prim's algorithm underlies network design tools that plan physical infrastructure — fiber-optic backbones, electrical grids, and water distribution networks — where the goal is connecting every site at minimum total cost. In computer vision, MST-based image segmentation algorithms use Prim's-style growth to cluster pixels into regions by treating pixel similarity as edge weight. Clustering algorithms in bioinformatics use minimum spanning trees, often built with Prim's algorithm on dense similarity graphs, to infer evolutionary or structural relationships between genetic sequences. Approximation algorithms for the metric traveling salesman problem construct a 2-approximate tour by first computing an MST — commonly via Prim's algorithm when the underlying graph is dense or given as a distance matrix — and then traversing it. Network routing protocols and circuit design tools for VLSI layout also invoke MST computation as a subroutine, frequently choosing Prim's algorithm specifically because chip layouts tend to produce dense, matrix-representable graphs where its $O(V^2)$ variant is fastest in practice.

:::quiz[What does key[v] represent during execution of Prim's algorithm?]

• The shortest path distance from the root to v
• The total number of edges explored so far
• The weight of the lightest edge connecting v to the current tree ✓
• The degree of vertex v in the final MST

Ask the tutor: How would you modify Prim's algorithm to efficiently support edge weight updates without recomputing the MST from scratch?