Prim's algorithm for minimum spanning trees - confusion in algorithm.

Question

I've been studying from the Cormen et al book and I'm a bit confused regarding the algorithm they have provided. I've understood how the concept of Prim's algo works through wikipedia, but I can't mimic that working using the algorithm provided in my book.

Refer to this online copy of the chapter: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf

The algo is given on page 13 in the above link and an example diagram is on the previous page.

Now, using the algorithm on the example case, in the first step:

u <--- node A through ExtractMin(Q). Then there are two entries in Adj[u] as per the diagram: node b and node h.

Now first set v <---- node b. Then check if v belongs to Q. It does. Check if w(u,v) < key[v]. True. So PI[v] <--- u and key[v] <--- w(u, v). I got this much. This is shown in (b) of the diagram on pg 12.

BUT the algo says "for each v in Adj[u]".

So the next step should set v <--- node h. Then check if v belongs to Q. It does! And is w(u,v) < key[v]? It is! Since key[v] = infinity! But the diagram shows a different step in part (c)!

Aaaaaah! Why?

Answer 1

Your description is correct, the algorithm does set key[h] = 8 as you describe in step a.

Step c has a key tie, you could pick h if you want, but the example picks c instead.

The best way to see it is to see what (non-infinite) elements are in the priority queue at each step (just before the ExtractMin):

1: Q = (a, 0)           - removes a, sets key[b]=4, key[h]=8
2: Q = (b, 4), (h, 8)   - removes b, sets key[c]=8
3: Q = (h, 8), (c, 8)   - could pick either h or c, they have the same key

Answer 2

One of the guys at MO was kind enough to answer by email. The problem was that I didn't notice that the tree nodes are added one at a time via the ExtractMin(Q) operation.

Here is the reply he gave:

*Your analysis is actually completely correct, but you (and I) were confused about what updating key[v] and pi(v) means. In particular, when you update pi(v), you do not add it to the tree. A node u is added to the tree (along the edge connecting it to its parent pi(u)) only when it is extracted from Q. So everything proceeds like you described, but at the end of it, you've only completed step (a), not step (c). Here's a run-down of what the program does in that case:

• (lines 1-3) All nodes are placed in Q (the set of nodes not in the tree), their parents are declared to be NIL, and their key (i.e. minimum distance to the existing tree along a single edge) is set to infinity
• (line 4) The key of the root node (node a) is set to 0
• (line 6) The node u with minimum key (which is the root node a) is removed from Q and added to the tree
• (lines 8-11) The keys of nodes b and h are updated to 4 and 8, and pi(b) and pi(h) are set to u (but b and h are not extracted from Q). This completes step (a)
• (line 6) The node u with minimum key (which is now node b, with key=4) is removed from Q and added to the tree via its parent (which is pi(b)=a)
• (lines 8-11) The key of nodes c is updated to 8, and pi(c) is set to b. Since key(h)=8 is smaller than 11=w(b,h), the key and parent of h are not updated. This completes step (b)
• (line 6) The node u with minimum key (node c, with key=8, but it could also have been node h, which also has key=8) is removed from Q and added to the tree via its parent (which is pi(c)=b)
• (lines 8-11) Update keys and parents of nodes d, i, and f, completing step (c)
• etc.*