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的实现，你可以检查，如果你想，但它稍微复杂一点，你在这里试图做什么。