0

我正在尝试在我的图形程序中实现 Prims 算法，但我遇到了一些困难。我正在遵循在此站点上找到的指南。

它似乎在某种程度上工作正常，但指南输出是：

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

 }
4

1 回答 1

1

这条评论：

// Initialize all keys as INFINITE

不符合代码的作用：

key[i] = -1;

因为您进一步使用此比较：

key[v] < min

如果key[v]是“无穷大” ，这将产生不同的结果。换句话说，这导致上述比较比它应该更频繁地为真。-1key[v]

可能还有更多问题 - 我没有详细检查，但使用pIndex看起来很可疑，例如。

于 2014-06-10T16:30:16.897 回答