Prim's algorithm

Grow one tree from a root using a min-priority queue keyed by the lightest edge to the tree. Vertex-centric, O(E lg V).

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:

u = EXTRACT-MIN(Q) — pull out the non-tree vertex with the lightest connecting edge; this commits the edge $(u, u . π)$ to the MST.
For each neighbor $v$ of $u$ still in $Q$ : if $w (u, v) < v . k ey$ , 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 (l g V)$ , giving $O (V l g V + E l g V) = O (E l g V)$ . A Fibonacci heap makes DECREASE-KEY $O (1)$ amortized, improving the bound to $O (E + V l g 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.)

Prim from root 0 on vertices 0, 1, 2, 6, 7, 8 of the exercise graph, immediately after EXTRACT-MIN(0) relaxes the root's edges. Each vertex's note is its key — the weight of the lightest edge joining it to the tree so far. Vertex 1 (key 4) is the next extraction, because Prim always pulls the smallest key.

Two extractions later the tree is {0, 1, 7} with edges 0–1 and 0–7 committed. Every remaining vertex shows the lightest edge joining it to that tree: 6 (key 1), 8 (key 7), 2 (key 8). Those candidate edges are dashed; EXTRACT-MIN takes 6 next and commits 7–6, the light edge crossing the cut ({0,1,7}, {2,6,8}).