Type the CLRS MST-PRIM pseudocode

Answer

for each u in G.V: u.key = INF; u.pi = NIL r.key = 0 Q = G.V # min-priority queue on 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.pi = u DECREASE-KEY(Q, v, w(u, v))

EXTRACT-MIN commits the lightest edge crossing the cut (tree vs non-tree) — safe by Corollary 21.2. The relaxation loop keeps each v.key equal to the lightest edge from v to the growing tree.