Prim's algorithm

Prim: grow a single tree

Where Kruskal manages many components, Prim grows one tree outward from a root $r$. Every non-tree vertex $v$ carries two attributes: v.key = the weight of the lightest edge connecting $v$ to the *current* tree (initially $\infty$, with r.key = 0), and v.π = the tree endpoint of that edge.

Keep all vertices in a min-priority queue $Q$ ordered by key. Repeat until $Q$ is empty:

1. u = EXTRACT-MIN(Q) — pull out the non-tree vertex with the lightest connecting edge; this commits the edge $(u, u.\pi)$ to the MST.
2. For each neighbor $v$ of $u$ still in $Q$: if $w(u,v) < v.key$, set v.key = w(u,v), v.π = u, and DECREASE-KEY(Q, v, w(u,v)).

Running time. $|V|$ EXTRACT-MINs and up to $|E|$ DECREASE-KEYs. With a binary min-heap each is $O(\lg V)$, giving $O(V\lg V + E\lg V)=O(E\lg V)$. A Fibonacci heap makes DECREASE-KEY $O(1)$ amortized, improving the bound to $O(E + V\lg V)$ — better for dense graphs.

Why it is correct

At each step the cut is $S = V-Q$ (vertices already in the tree) versus $Q$. Every $A$-edge lies inside $S$, so the cut respects $A$. EXTRACT-MIN returns the vertex whose connecting edge is the *light edge* crossing $(S, V-S)$, so by Corollary 21.2 the committed edge is safe. This is the same proof skeleton as Dijkstra — extract the minimum-key vertex, then relax its neighbors. Prim and Dijkstra differ only in the key formula: Prim uses $w(u,v)$ (edge weight to the tree); Dijkstra uses $u.d + w(u,v)$ (cumulative distance from the source).

Worked example

Running Prim from vertex 0 on the same CLRS Fig 21.4 graph chooses a different *set* of edges than Kruskal in general, but the total is identical: 37. (An MST's weight is unique even when the tree is not.)