title: Prim's algorithm for minimum spanning trees - confusion in algorithm
body: <p>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.</p>
  
  <p>Refer to this online copy of the chapter:
  <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf" rel="nofollow noreferrer">http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf</a></p>
  
  <p>The algo is given on page 13 in the above link and an example diagram is on the previous page.</p>
  
  <p>Now, using the algorithm on the example case, in the first step:</p>
  
  <p>u &lt;--- node A through ExtractMin(Q).
  Then there are two entries in Adj[u] as per the diagram: node b and node h.</p>
  
  <p>Now first set v &lt;---- node b. Then check if v belongs to Q. It does. Check if w(u,v) &lt; key[v]. True. So PI[v] &lt;--- u and key[v] &lt;--- w(u, v).
  I got this much. This is shown in (b) of the diagram on pg 12.</p>
  
  <p>BUT the algo says "for each v in Adj[u]".</p>
  
  <p>So the next step should set v &lt;--- node h.
  Then check if v belongs to Q. It does! And is w(u,v) &lt; key[v]? It is! Since key[v] = infinity!
  But the diagram shows a different step in part (c)!</p>
  
  <p>Aaaaaah! Why?</p>