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 Q based on a key attribute.
- v.key is the minimum weight of any edge connecting v to a vertex in the tree
- v.π points to the parent of v in the tree
- G is a graph, w is a weight function, r is 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?
Asked By : Mahesha999
Answered By : hengxin
Question 1: 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$.
You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$.
- All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = emptyset$ at this time point.
- A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.
- In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are not inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).
Question 2: “My point is when the line 8 says “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$).”
Yes, $h$ is also considered, but in the way different from what you describe. In the iteration for $a$, both $b$ and $h$ are considered (satisfying Line 8 and Line 9): their keys are updated (i.e., decreased) in the priority queue $Q$ (Line 11) and their parents are updated accordingly (Line 10). (Note that these updates are not finalized and may be updated again during the algorithm.) The key point is: neither $b$ nor $h$ has been added into the resulting MST tree $T$. Vertex $b$ will be extracted from $Q$ and added into $T$ in the next iteration at Line 7 (shown in step (b)). Also note that the figure in CLRS only shows the changes on $T$; it does not show the states of $Q$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/50964 Ask a Question Download Related Notes/Documents
