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

if you do not want to use PriorityQueue, here is my implementation of Heap in Java.. you can replace PriorityQueue with MinHeap.

package algo2;

import java.io.DataInputStream;
import java.io.InputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Prims {

private static final class GNode implements Comparable<GNode> {
    // unique id of the node
    int id;

    // map of child nodes and their respective distance from current node 'id'
    Map<GNode, Integer> children = new HashMap<GNode, Integer>();

    // used in future computation, to store minimal/optimal updated distance
    int distFromParent=0;

    public GNode(int i) {
        this.id=i;
    }

    @Override
    public int compareTo(GNode o) {
        return this.distFromParent-o.distFromParent;
    }

    @Override
    public String toString() {
        return "GNode [id=" + id + ", distFromParent=" + distFromParent
                + "]";
    }
}

static long findLengthOfMST(GNode[] nodes) {
    PriorityQueue<GNode> pq = new PriorityQueue<GNode>();
    boolean[] visited = new boolean[nodes.length];
    boolean[] exited = new boolean[nodes.length];
    pq.add(nodes[1]);
    visited[1] = true;
    long sum = 0;
    int count = 0;
    while (pq.size() > 0) {
        GNode o = pq.poll();
        if (!exited[o.id]) {
            for (GNode n : o.children.keySet()) {
                if (exited[n.id]) {
                    continue;
                }
                if (visited[n.id]) {
                    if (n.distFromParent >= o.children.get(n)) {
                        n.distFromParent = o.children.get(n);
                    }
                } else {
                    visited[n.id] = true;
                    n.distFromParent = o.children.get(n);
                    pq.add(n);
                }
            }
            sum += o.distFromParent;
            exited[o.id] = true;
            count++;
        }
        if (pq.size() == 0) {
            for (int i = 1; i < nodes.length; i++) {
                if (!exited[i]) {
                    pq.add(nodes[i]);
                }
            }
        }
    }
    System.out.println(count);
    return sum;
}

public static void main(String[] args) {
    StdIn s = new StdIn(System.in);
    int V = s.nextInt();
    int E = s.nextInt();
    GNode[] nodes = new GNode[V+1];
    for (int i = 0; i < E; i++) {
        int u = s.nextInt();
        int v = s.nextInt();
        GNode un = nodes[u];
        GNode vn = nodes[v];
        if (un == null) {
            un = new GNode(u);
            nodes[u] = un;
        }
        if (vn == null) {
            vn = new GNode(v);
            nodes[v] = vn;
        }

        int w = s.nextInt();
        un.children.put(vn, w);
        vn.children.put(un, w);
    }
    long len = findLengthOfMST(nodes);
    System.out.println(len);
}

private static class StdIn {
    final private int BUFFER_SIZE = 1 << 17;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;
    public StdIn(InputStream in) {
    din = new DataInputStream(in);
    buffer = new byte[BUFFER_SIZE];
    bufferPointer = bytesRead = 0;
    }
    public int nextInt() {int ret = 0;byte c = read();while (c <= ' ')c = read();boolean neg = c == '-';if (neg)c=read();do{ret=ret*10+c-'0';c = read();} while (c>' ');if(neg)return -ret;return ret;}
    private void fillBuffer(){try{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);}catch(Exception e) {}if(bytesRead==-1)buffer[0]=-1;}
    private byte read(){if(bufferPointer == bytesRead)fillBuffer();return buffer[bufferPointer++];}
    }
}

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.

Answer 3

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.