Prim's Algorithm

Prim’s algorithm builds an MST by growing a single tree from an arbitrary root, repeatedly adding the lightest edge connecting the tree to a vertex outside. It is structurally similar to Dijkstra’s algorithm but uses direct edge weights rather than cumulative path distances.

Algorithm

PRIM(G, w, r):
    for each v in G.V:
        v.key = INFINITY
        v.parent = NIL
    r.key = 0
    Q = priority queue containing all vertices, keyed by v.key
    while Q is not empty:
        u = EXTRACT-MIN(Q)
        for each v in G.adj[u]:
            if v in Q and w(u, v) < v.key:
                v.parent = u
                v.key = w(u, v)
                DECREASE-KEY(Q, v, v.key)

At termination, the edge set $\{(v.\text{parent}, v) \mid v \neq r, v.\text{parent} \neq \text{NIL}\}$ forms the MST.

Key Insight

The key of a vertex is the minimum weight of any edge connecting it to the current tree. This differs from Dijkstra, where key is the cumulative distance from the source. In Prim, the key is just the single edge weight, not a path sum.

Correctness

The algorithm maintains the invariant: at the start of each loop iteration, for every vertex not yet extracted, its key is the minimum-weight edge connecting it to the tree (vertices already extracted). When EXTRACT-MIN selects $u$, the edge $(u.\text{parent}, u)$ is the lightest edge crossing the cut (current tree, rest of graph), so it is a safe edge. The correctness follows from the safe-edge theorem.

Formally, at each step the set $S$ of extracted vertices forms a tree, and the cut $(S, V \setminus S)$ is respected by the tree edges. The extracted vertex $u$ is connected via the lightest edge crossing this cut.

Running Time

Using a binary heap:

• Initialisation: $O(|V|)$, or $O(|V|)$ for BUILD-HEAP
• $|V|$ EXTRACT-MIN operations: $O(|V| \log |V|)$
• Up to $|E|$ DECREASE-KEY operations, each $O(\log |V|)$: $O(|E| \log |V|)$
• Queue membership test via bit array: $O(1)$ per check

Total: $O(|V| \log |V| + |E| \log |V|) = O(|E| \log |V|)$ for connected graphs.

Using a Fibonacci heap:

• EXTRACT-MIN: amortised $O(\log |V|)$
• DECREASE-KEY: amortised $O(1)$

Total: $O(|V| \log |V| + |E|)$, which is better for dense graphs where $|E| = \Theta(|V|^2)$. The $O(|E|)$ term dominates.

Worked Example

Same graph as the Kruskal example: vertices $\{A, B, C, D, E, F\}$, root $A$.

Edges: $A-B:4$, $A-C:1$, $B-C:3$, $B-D:2$, $C-D:5$, $C-E:6$, $D-E:7$, $D-F:4$, $E-F:3$.

Initialise: key($A$) = 0, all others $\infty$. Queue: all vertices.

1. Extract $A$ (key 0). Update neighbours: key($B$) = 4, key($C$) = 1. Parents: $B \leftarrow A$, $C \leftarrow A$.
2. Extract $C$ (key 1). Update neighbours: key($B$) $\leftarrow$ min(4, 3) = 3 (parent $C$), key($D$) = 5 (parent $C$), key($E$) = 6 (parent $C$).
3. Extract $B$ (key 3). Update neighbours: key($D$) $\leftarrow$ min(5, 2) = 2 (parent $B$).
4. Extract $D$ (key 2). Update neighbours: key($E$) $\leftarrow$ min(6, 7) = 6 (no change), key($F$) = 4 (parent $D$).
5. Extract $F$ (key 4). Update neighbours: key($E$) $\leftarrow$ min(6, 3) = 3 (parent $F$).
6. Extract $E$ (key 3). No unextracted neighbours.
7. Queue empty.

MST edges: $(A,C)$, $(C,B)$, $(B,D)$, $(D,F)$, $(F,E)$. Total weight: $1 + 3 + 2 + 4 + 3 = 13$ (same total as Kruskal via different tree shape).

Prim vs. Dijkstra

Aspect	Prim	Dijkstra
Key meaning	Weight of connecting edge	Cumulative distance from source
Initialisation	root.key = 0	s.d = 0
Relax condition	w(u, v) < v.key	u.d + w(u, v) < v.d
Update	v.key = w(u, v)	v.d = u.d + w(u, v)
Handles	Connected undirected graphs	Directed graphs, non-negative weights
Output	MST (tree of minimum total weight)	Shortest path tree

Summary

Aspect	Binary heap	Fibonacci heap
EXTRACT-MIN	$O(\log \lvert V \rvert)$	$O(\log \lvert V \rvert)$ amortised
DECREASE-KEY	$O(\log \lvert V \rvert)$	$O(1)$ amortised
Total	$O(\lvert E \rvert \log \lvert V \rvert)$	$O(\lvert V \rvert \log \lvert V \rvert + \lvert E \rvert)$
Best for	Sparse graphs	Dense graphs ($\lvert E \rvert = \Theta(\lvert V \rvert^2)$)

Past Tripos: y2024p2q7, y2023p1q9.