= Solution
<Prim's algorithm> grows a tree from any root $r$. For each vertex outside the current tree, its <priority queue> key is the cheapest single edge connecting it to the tree, not the total length of a root-to-vertex path:
``
for v in V:
key[v] = infinity
parent[v] = NONE
key[r] = 0
Q = indexed_min_priority_queue(V, key)
while Q is not empty:
u = Q.extract_min()
for (v,weight) in adjacency[u]:
if Q.contains(v) and weight < key[v]:
parent[v] = u
key[v] = weight
Q.decrease_key(v, weight)
return {(parent[v],v) : v != r}
``
The <indexed priority queue> supports membership and locating a vertex's heap entry. After the first extraction, the chosen parent edge is a least-weight edge crossing the cut between the current tree and its complement. The <minimum spanning tree cut property> makes that edge safe: exchanging it for a crossing edge of a suitable minimum tree preserves minimality. Repeating this establishes a minimum tree. Connectivity ensures every nonroot vertex eventually has a parent; edge weights may be negative.
Back to article page
