Take the 2-minute tour ×
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]
            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.

share|improve this question
Slightly offtopic: if you just want a nifty maze, why not try the classical DFS generator? It's dead simple, pretty efficient, and produces a completely random maze, which tends to be hard to solve. –  Vilx- Jul 18 '12 at 8:03
I'll definitely look into other methods of maze generation if I ever figure this out, but at this point with this problem - its personal. –  user595334 Jul 18 '12 at 8:26
OK, good luck! :) –  Vilx- Jul 18 '12 at 9:44

1 Answer 1

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);,

share|improve this answer

Your Answer

