CODEWITHSUNDEEP
calgorithmgraph-algorithmpriority-queueprims-algorithm
user595334
user595334

Reputation:

Prim's Algorithm with Priority Queues implementation

void PrimMST(float A[GsizeSqr][GsizeSqr])
{
    int i, j, pCount, gs, row, ind, findN;
    gs = sqrt(GsizeSqr);
    pCount = 0;

    D_array MST; //MST contains the nodes of the MST and is initialized with the starting node
    initArr(&MST, 1);
    int p[GsizeSqr];
    float priority[GsizeSqr]; //priority contains weight(u, p[u])

    //Initialize p and priority with infinity and NULL values (note: -1 means null and 1000000 means inf)
    for(i=0; i < GsizeSqr; i++){
        p[i] = -1;
        priority[i] = 1000000;
    }

    PriorityQueue Q; //Initialize priority queue that stores (priority, key) values
    Q = init_heap(GsizeSqr);    
    for(i=0; i < gs; i++){ //Insert input adjacency matrix into priority queue
        for(j=0; j < gs; j++){
            node n;
            n = create_node(A[i][j], pCount++);
            enqueue(Q, n);          
        }
    }

    node start; //Select starting node and insert to MST
    start = create_node(0, 0);
    insArr(&MST, start);

    priority[0] = 0;

    while(Q->heap_size != 1){ //while Q not empty
        node u;
        u = dequeue(Q);
        if(p[u.key] != -1)
            insArr(&MST, u);

        row = ceil(u.key/gs);
        //For each adjacent node A[row][i]
        for(i=0; i < gs; i++){
            if(A[row][i] != 0.0){
                ind = i*gs + row; //Calculate index of adjacent node
                findN = find_node(Q, ind); //find and return index of adjacent node in queue

                if(findN != 0 && u.priority < Q->elements[findN].priority){
                    set_priority(Q, findN, u.priority);
                    p[findN] = u.key;                   
                }               
            }
        }
    }   
}

I am trying to create a C implementation of Prim's Algorithm using priority queues using the pseudocode which is similar to many sources online. The end goal is (hopefully) some nifty maze generation. I'm just having confusion with the details of the implementation.

input: An adjacency matrix with random weights

desired output: The adjacency matrix for a minimal spanning tree

*EDIT: Added my (not working) attempt. I'm still getting an incorrect tree, I'm not sure where I'm going wrong. I think I would benefit from another set of eyes over this code.

Upvotes: 2

Views: 5083

Answers (1)

Marcus
Marcus

Reputation: 6839

first question: A is the set that contains the edges of the MST. p[u] means which node has the minimum edge with u currently, that is to say, if you have three edges(node 1, node 2, weight) (1,2,5), (1,3,4), (1,4,10), then p[1] = 3, and now priority[1] is 4.

second one: nope, the node is pop after u := EXTRACT-MIN(Q);,

Upvotes: 1

Related Questions