C++：BFS來計算樹中每一對節點之間的距離

Question

我有一個加權樹N頂點以鄰接表的形式存儲。我有一個M節點的列表。

我們計算的每對節點之間的距離M個節點的列表中此樹是我寫了這個：

using namespace std; 
#define MAX_N (1<<17) 
#define MAX_V (1<<17) 

typedef pair<int,int> pii;  
vector<pii> adj[MAX_V]; 

bool vis[MAX_N]; //mark the node if visited 
ll bfs(pii s,pii d) 
{ 
    queue <pii> q; 
    q.push(s); 
    ll dist=0; 

    vis[ s.first ] = true; 
    while(!q.empty()) 
    { 
     pii p = q.front(); 
     q.pop(); 
     for(auto i = 0 ; i < adj[ p ].size() ; i++) 
     { 
      if(vis[ adj[ p ][ i ].first ] == false) 
      { 
       q.push(adj[ p ][ i ].first); 
       vis[ adj[ p ][ i ] ] = true; 
       dist += adj[p][i].second; 
      } 


     } 
    } 

    return dist; 
} 

int main() 
{ 

     for(int i=0;i<N;i++) 
     { 
      int v1,v2,l; 
      cin>>v1>>v2>>l; 
      adj[v1].push_back(make_pair(v2,l)); 
      // adj[v2].push_back(make_pair(v1,l)); 
     } 
     int a[M]; 
     for(int i=0;i<M;i++) 
     cin >> a[i]; 

     int ans=0; 


     for(int i=0;i<M-1;i++) 
     { 
      for(int j=i+1;j<M;j++) 
      { 
       num += bfs(adj[a[i]],adj[a[j]]); 
      } 
     } 

    } 

程序不編譯錯誤如下：

could not convert 'adj[a[i]]' from 'std::vector<std::pair<long long int, long long int> >' to 'pii {aka std::pair<long long int, long long int>}' 
       num += bfs(adj[a[i]],adj[a[j]]); 

另外我知道這個程序在計算BFS時是錯誤的，因爲它在到達目的頂點時沒有停止。

有人可以幫我解決這些錯誤嗎？

Answer 1

我覺得有幾個問題：

• for(auto i = 0 ; i < adj[ p ].size() ; i++)您使用數p作爲指數爲形容詞，但p是pii型的。你可能想要p.first，假設這些對有意義（從，到）
• if(vis[ adj[ p ][ i ].first ] == false)：我假設你想檢查鄰居是否還沒有被訪問。所以它應該更像這樣：vis[adj[p.first][i].second] == false。訪問的索引是adj[p.first][i].second。我正在檢查第二個，因爲我假設（從，到）
• q.push(adj[ p ][ i ].first);的語義：您正在推送一個整數，但隊列中保存的類型爲pii。由你決定如何改變它。
• dist += adj[p][i].second;：您正在使用該對索引數組。如Buckster在您傳遞vector<pii>，而不是pii到的bfs功能

這些只是編譯問題雖然已經註釋說明你應該使用索引

最後num += bfs(adj[a[i]],adj[a[j]]);。我不確定你的算法實際上是否符合你的期望。您可以使用bfs來計算任意兩個節點之間的距離，但是如果它是加權的，則bfs本身不會爲您提供最小路徑。如果你對最小路徑感興趣，你可以使用Dijkstra，前提是權重是正的。 Here我有一個bfs的實現，你可以檢查，如果你想，但它稍微複雜一點，你在這裏試圖做什麼。