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;                   
                }               
            }
        }
    }   
}

我正在尝试使用类似于许多在线资源的伪代码使用优先级队列创建 Prim 算法的 C 实现。最终目标是（希望）一些漂亮的迷宫生成。我只是对实施的细节感到困惑。

输入：具有随机权重的邻接矩阵

期望输出：最小生成树的邻接矩阵

*编辑：添加了我的（不工作）尝试。我仍然得到一棵不正确的树，我不确定我哪里出错了。我想我会从对这段代码的另一组眼睛中受益。

4

1 回答 1

1

第一个问题：A 是包含 MST 边的集合。p[u] 表示当前哪个节点与u的边最小，也就是说，如果你有3条边（节点1，节点2，权重）（1,2,5），（1,3,4）， (1,4,10)，然后 p[1] = 3，现在 priority[1] 为 4。

第二个：不，节点在之后弹出u := EXTRACT-MIN(Q);，

于 2012-07-18T02:52:50.760 回答