在C + + STL錯誤Prim的算法實現？

我想在C++中使用STL實現Prim的MST算法。在C + + STL錯誤Prim的算法實現？

但是對於下面的程序，它似乎進入了一個無限循環。然後退出時出現錯誤。

Prim的MST算法的僞代碼;

enter image description here

我的代碼：

#include<algorithm> 
#include<vector> 
#include<iostream> 
#include<queue> 
using namespace std; 

typedef vector<int>   vi; 
typedef pair<int,int>  ii; 
typedef vector<ii>   vii; 

#define REP(i,a,b) for(int i=int(a);i<b;i++) 
#define TRvii(c,it) for(vii::iterator it=(c).begin();it!=(c).end();it++) 

#define INF 2000000000 

void Prims(int V, int s, vector<vii> &AdjList) 
{ 
    vector<int> dist(V,INF); 
    dist[s] = 0; 
    priority_queue<ii,vector<ii>,greater<ii> > pq; 
    pq.push(ii(0,s)); 

    REP(i,1,V) pq.push(ii(i,INF)); 

    bool inPriorityQueue[V]; 
    REP(i,0,V) inPriorityQueue[i] = true; 

    while(!pq.empty()) 
    { 
     ii top = pq.top(); pq.pop(); 
     int d = top.first,u = top.second; 

     inPriorityQueue[u] = false; 

     TRvii(AdjList[u],it) 
     { 
      int v = it->first, weight_u_v = it->second; 

      if(inPriorityQueue[v] && weight_u_v<dist[v]) 
      { 
       dist[v] = weight_u_v; 
      } 
     } 
    } 

    cout << "The shortest distance from " << s << " to all the nodes is" << endl; 
    REP(i,0,V) 
    { 
     cout << i << " : " << dist[i] << endl; 
    } 
} 

int main() 
{ 
    int v,s,edges; 

    printf("Enter number of vertices : "); 
    scanf("%d",&v); 

    vector<vii> adjList(v+1); 

    printf("\nEnter source vertex : "); 
    scanf("%d",&s); 

    adjList[0].push_back(make_pair(1,4)); 
    adjList[0].push_back(make_pair(7,8)); 
    adjList[1].push_back(make_pair(0,4)); 
    adjList[1].push_back(make_pair(2,8)); 
    adjList[1].push_back(make_pair(7,11)); 
    adjList[7].push_back(make_pair(0,8)); 
    adjList[7].push_back(make_pair(1,11)); 
    adjList[7].push_back(make_pair(8,7)); 
    adjList[7].push_back(make_pair(6,1)); 
    adjList[2].push_back(make_pair(1,8)); 
    adjList[2].push_back(make_pair(3,7)); 
    adjList[2].push_back(make_pair(8,2)); 
    adjList[2].push_back(make_pair(5,4)); 
    adjList[8].push_back(make_pair(2,2)); 
    adjList[8].push_back(make_pair(7,7)); 
    adjList[8].push_back(make_pair(6,6)); 
    adjList[6].push_back(make_pair(7,1)); 
    adjList[6].push_back(make_pair(5,2)); 
    adjList[6].push_back(make_pair(8,2)); 
    adjList[5].push_back(make_pair(6,2)); 
    adjList[5].push_back(make_pair(2,4)); 
    adjList[5].push_back(make_pair(3,14)); 
    adjList[5].push_back(make_pair(4,10)); 
    adjList[4].push_back(make_pair(3,9)); 
    adjList[4].push_back(make_pair(5,10)); 
    adjList[3].push_back(make_pair(2,7)); 
    adjList[3].push_back(make_pair(5,14)); 
    adjList[3].push_back(make_pair(4,9)); 

    Prims(v, s, adjList); 

    return 0; 
}

圖上這個算法實現：

enter image description here

來源

2014-10-20 Akash Rana

小費：如果你想要大數目表示無窮大，那麼我建議['std :: numeric_limits :: max']（http://en.cppreference.com/w/cpp/types/numeric_limits/最大）。 – 2014-10-20 11:30:42

什麼是錯誤？ – tgmath 2014-10-20 11:31:04

至於你的問題，從一組較小的輸入數據（圖）開始，並在調試器中逐行執行代碼，以查看發生了什麼。 – 2014-10-20 11:32:40

如果你曾試圖調試它，你會很快發現問題位於該行：

TRvii(AdjList[u],it)

想想u是什麼。在while迴路u == s由於pq.push(ii(0,s));第一次。然而，在接下來的所有循環中，由於REP(i,1,V) pq.push(ii(i,INF));而導致u == INF。

試圖訪問AdjList[INF]是「不好」，並導致未定義的行爲（在您的情況下崩潰）。

我建議進一步調試你的算法，可能用一個更簡單的測試用例。逐步瀏覽並觀察所有變量。大概你理解算法和它應該經過的狀態，注意所有變量以確保它們應該是什麼。

來源

2014-10-20 11:53:54 uesp

在C + + STL錯誤Prim的算法實現？

回答

相關問題