Prim's Algorithm with matrices

Question

I am trying to implement Prim's algorithm with C++ and matrices.

Here is my problem:

int node[] = {11, 11, 0, 11, 11, 11, 11, 11};
int nodeCon[8];

void generatePrims() {
    int cNode = 3;

    for (int i = 1; i <= 8; i++) {

        if (graph[cNode][i] != 0){

            if (node[i] > graph[cNode][i]) {
                node[i] = graph[cNode][i];
                nodeCon[i] = cNode;
                }
            }
        }
};

cNode is the starting node.

graph[][] is the 2d matrices that holds the connections.

nodeCon[] is the array that will hold the connections for the MST (which node is connected with other)

node[]= holds the cost-value for the nodeCon.

My question is how I am going to continue to the next hop? Let's say that I found the minimum connection and I will set the value cNode= minConnection how the loop is going to look? How I know that I had examine all the nodes?

Thanks in advance

Answer 1

Something like this:

int node[]={11,11,0,11,11,11,11,11};
int used[]={0,0,0,0,0,0,0,0,0,0};
int nodeCon[8];

void generatePrims(){
   int cNode = 3;
   int next, min_now;
   for(int i=0; i<8; ++i) {
      used[cNode] = 1;
      min_now = MAX_INT;
      for(int i=1;i<=8;i++){
         if(!used[i]){ 
            if(node[i] > graph[cNode][i]){
               node[i] = graph[cNode][i];
               nodeCon[i]= cNode;
            }
            if(node[i] < min_now) {
               min_now = node[i];
               next = i;
            }  
         } 
      }
      cNode = next;
   }
};

Also worth noting: it will be faster if instead of array 'used' you will use a list of unused vertices.

Answer 2

I can't currently comment on the previous answer (as I don't have enough reputation) so I will do it through another answer. Piotr solution is almost correct however I believe Prim's algorithm takes into account more than just the current node. An example can be seen here Prim's Algorithm. What this essentially means is you need to check the path from nodes you have visited not just the most recent node.

This means you will need to store a vector containing the nodes you have visited and "for each" through them as opposed to just checking the paths from the last node you visited.

Answer 3

The following site has the algorithm inplemented and a junit test class. So it should be what you are looking for. The unit test class has an actual matrix, of course. And the implementation class has the code.

http://www.geekviewpoint.com/java/graph/mst