Implementation of Prim's Algorithm

Question

For my CS class I need to implement Prim's algorithm in Java and I am having problems with the priority queue step. I have experience with priority queues and understand they work in general but I am having trouble with a particular step.

Prim(G,w,r)
  For each u in V[G]
    do key[u] ← ∞ 
       π[u] ← NIL  
  key[r] ← 0
  Q ← V[G]  
  While Q ≠ Ø
    do u ← EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

I've created a Node class that contains the key value(which I assume is the lightest edge connected to the Node) and the parent Node. My problem is that I don't understand adding the Node to the priority queue. Adding all the Nodes to the priority queue doesn't not make sense to me when the parent has been set to NIL and the key to ∞.

Answer 1

You needn't worry about adding all the nodes to the priority queue even if they have infinite keys; they will eventually be lowered by DECREASE_KEY on the last line of your pseudocode. You would need this operation anyway, so there's no reason not to simplify your life and insert them all at once.

I see only one problem with your pseudocode, namely, that it will behave strangely on disconnected graphs.

Answer 2

In the pseudocode in your question, key[u] and π[u] are the set of values that will represent the minimum spanning tree of G when the algorithm is finished. The values are initialized to ∞ and NIL respectively at the beginning of the algorithm to signify that no vertices have yet been added to the MST. The next step sets the root element (key[r] ← 0).

The priority queue Q is a separate data structure from key and π. Q should be initialized with all of the vertices in the original graph G, not the values in key and π. Note that you will need more information than just the lightest edge and parent node for each vertex, since you need to know all the vertices adjacent to each one you extract from Q.