c - Prim的算法

我正在尝试将prims alghoritm实现到我的图形程序中，但是我遇到了一些困难，我遵循的指南是
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
它似乎在某种程度上运行良好，但指南输出是：

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

我的解决方案是：

Edge   Weight
1 - 0    2
1 - 2    3
1 - 3    8 <---- this one seems off.
1 - 4    5

我真的不知道我的代码有什么问题。
我的代码是：

void b_Prim(){
    reset_adjmat(G); // resets current adjmat and creates a new one.
    int V = b_card(G); // b_card = cardinality
    int count, i, v, u, min_index, min = -1,pIndex = 1;
    int key[V];   // Key values used to pick minimum eWeight edge in cut
    int mstSet[V];  // To represent set of vertices not yet included in MST

 // Initialize all keys as INFINITE
 for (i = 0; i < V; i++){
    key[i] = -1;
    mstSet[i] = 0;
 }
 // Always include first 1st vertex in MST.

 key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex
 source[0] = -1; // First node is always root of MST

 // The MST will have V vertices
 for (count = 0; count < V-1; count++)
 {
    // Pick thd minimum key vertex from the set of vertices
    // not yet included in MST
       for (v = 0; v < V; v++)
            if (mstSet[v] == 0 && ((min == -1 && key[v] != -1) || key[v] < min)){
                min = key[v];
                min_index = v;
            }

    u = min_index;

    // Add the picked vertex to the MST Set

   mstSet[u] = 1;

    // Update key value and source index of the adjacent vertices of
    // the picked vertex. Consider only those vertices which are not yet
    // included in MST
    for (v= 0; v < V; v++)

       // graph[u][v] is non zero only for adjacent vertices of m
       // mstSet[v] is false for vertices not yet included in MST
       // Update the key only if graph[u][v] is smaller than key[v]

      if (adjmat[u][v] != 0 && mstSet[v] == 0 && (key[v] == -1 || adjmat[u][v] <  key[v])){
         source[pIndex]  = u;
         dest[pIndex] = v;
         key[v] = adjmat[u][v];
         eWeight[pIndex] = key[v];
         pIndex++;
     }else if(adjmat[u][v] != 0 && mstSet[v] == 0 && key[v] == 0){
         source[pIndex]  = u;
         dest[pIndex] = v;
         eWeight[pIndex] = adjmat[u][v];
         pIndex++;
     }
 }

 }

最佳答案

此评论：

// Initialize all keys as INFINITE

与代码不对应：

key[i] = -1;

由于您进一步使用此比较：

key[v] < min

如果key[v]是-1将产生不同的结果，而如果key[v]是“无穷大”，则会产生不同的结果。换言之，这会导致上述比较的真实性大大提高。
可能还有更多的问题-我还没有详细检查，但使用pIndex看起来可疑，例如。

关于c - Prim的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24145687/