2 
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.

4

1 に答える 1

1

最初の質問: A は、MST のエッジを含むセットです。p[u] は、現在 u で最小のエッジを持つノードを意味します。つまり、3 つのエッジ (ノード 1、ノード 2、重み) (1,2,5)、(1,3,4)、 (1,4,10) の場合、p[1] = 3 になり、優先度 [1] は 4 になります。

2 つ目: いいえ、ノードは後u := EXTRACT-MIN(Q);にポップされます。

于 2012-07-18T02:52:50.760 に答える