3
$\begingroup$

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 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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ Your doubt is very similar to mine. I think they don't use their own algorithm with min-priority queue but simply apply the blue rule until the tree includes all the $n$ nodes of the graph. Then follows your (and mine) confusion. $\endgroup$ – kentilla Dec 20 '15 at 10:51
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I think I understand all those point. My point is when 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$). Am I making any sense? $\endgroup$ – anir123 Dec 20 '15 at 14:45
  • $\begingroup$ @Mahesha999 please, visit this link (R. Sedgewick, K. Wayne. "Algorithms"). He first states Prim's algorithm and then introduces the concepts of lazy and eager implementation where the process is clearly explained. If you look at PrimMST.java it's all in all the same algorithm you reported from CLRS and, in your example, it would add both nodes $b$ and $h$ (try it in debug). So my conclusion is that the example reported in the picture is not related to how the PQ implementation builds incrementally the solution. $\endgroup$ – kentilla Dec 20 '15 at 23:54
  • $\begingroup$ @Mahesha999 see "Question 2" of my updated answer. $\endgroup$ – hengxin Dec 21 '15 at 2:01
  • $\begingroup$ @kentilla You probably misunderstood the eager Prim's algorithm. The red&thin lines in that figure for eager Prim are not for indicating the vertices that will be added into the resulting MST tree; they are showing the state of the priority queue. $\endgroup$ – hengxin Dec 21 '15 at 2:09
  • $\begingroup$ ohh right, inside if only π and v are updated, but the node is added to the key only at the start of the next iteration. But just guessing, $h$ is enqueued first and then $c$, so should $h$ be dequeued before $c$ when EXTRACT-MIN() is called (I know that must be implementation specific to EXTRACT-MIN(), but isn't it the standard when two elements have same value in priority queue then dequeue the oldest one i.e. the one first enqueued), so still adding $h$ to tree before $c$? $\endgroup$ – anir123 Dec 21 '15 at 13:57
0
$\begingroup$

I've done some simulation, implementing Prim's algorithm exactly as you reported from CLRS. As the book says, you have a set $A$ implicitly maintained by the algorithm, defined as

$$ A = \{(v, v.\pi) : V-\{r\} - Q \} $$

This is built incrementally, and when the priority Q is empty then it is complete. Here is the output of my simulation with the same instance of the book, starting from node 'a': gray circles represent nodes already included in the MST (actually, I included also the starting node), while bold lines represents eligible edges for the solution. White circles are nodes in the queue. As long as PQ is consumed, adjustment are done. Note that you aren't building the MST when you update the $\pi$ attribute if nodes are still in the queue (see $A$ definition).

Prim's algorithm example

The total cost of the MST is $37$, as you can see this graph has more than one MST.

$\endgroup$
  • $\begingroup$ Using which software / tool you run prims on the graph above? (above diagram seems to be the execution of algo using some tool) $\endgroup$ – anir123 Mar 20 '17 at 7:11
0
$\begingroup$

As both of vertices are present in Q with same key value 8, So you can either choose (b,h) or (b,c). Resultant MST will be same in both cases.

$\endgroup$
  • 2
    $\begingroup$ How does this add to hengxin's answer? $\endgroup$ – Yuval Filmus Mar 17 '17 at 10:49
0
$\begingroup$

In simple words, the line $7$ which is extracting a vertex $v$ tells the next vertex to be added in the tree. $h$ vertex is extracted after $g$. Although the parent of $h$ would be written $a$ (i.e, $h.\pi = a$) during first iteration but it eventually be overwritten when $g$ would aspect it forwardly (i.e, $h.\pi = g$). Also, note that $... if \ v \in Q...$ in the $9$ the line is another interesting thing; it ensures to follow cut property.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.