Prims alghoritm

Question

我正嘗試實施Prims Alghoritm我的圖形程序，但我用起來有些困難，下面的指導，我發現在 http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

這似乎是工作的罰款在一定程度上的IM，但導遊輸出爲：

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

} 

Answer 1

此評論：

// Initialize all keys as INFINITE 

不對應的代碼做什麼：

key[i] = -1; 

，因爲你還用這種比較：

key[v] < min 

如果key[v]爲-1，將會產生不同的結果，如果key[v]爲'無窮大'，那麼結果將會是預期的。換句話說，這導致上述比較比其應該更經常得多。

可能有更多的問題 - 我沒有詳細檢查，但使用pIndex看起來可疑，例如。