The algorithm is as follows:
MST-PRIM(G,w,r) 1 for each u ∈ G.V //initialization 2 u.key = ∞ 3 u.π = NIL 4 r.key = 0 5 Q = G.V //end initialization 6 while Q ≠ ∅ 7 u = EXTRACT-MIN(Q) 8 for each v ∈ G.Adj[u] 9 if v ∈ Q and w(u,v) < v.key 10 v.π = u 11 v.key = w(u,v)
- All vertices that are not in the tree reside in a min-priority queue
Qbased on a
v.keyis the minimum weight of any edge connecting
vto a vertex in the tree
v.πpoints to the parent of
vin the tree
Gis a graph,
wis a weight function,
ris a root
The example given is as follows:
I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:
In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.
However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.
The line 8 says
for **each v** ∈ G.Adj[u](i.e. for each adjacent vertex $v$ of $u$), why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$).
If what author says should occur, then there should be something like
break construct on line 12 inside the
if construct's body, which will result in exiting
for loop and hence grabbing next
u = EXTRACT-MIN(Q).
Am I correct? or I must be missing something very stupid. What's that?