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作为adj的索引，但p属于pii类型。您可能希望p优先，假设这对具有含义(from, to)
• if(vis[ adj[ p ][ i ].first ] == false):我假设你想检查邻居是否还没有被访问。所以它应该是这样的:vis[adj[p.first][i].second] == false。访问的索引是adj[p.first][i].second。我检查第二，因为我假设语义为(from, to)对
• q.push(adj[ p ][ i ].first);:您正在推送一个整数，但队列保存类型为pii。你想怎么改变它取决于你。
• dist += adj[p][i].second;:您正在使用对索引数组。你应该使用索引
• 最后num += bfs(adj[a[i]],adj[a[j]]);，正如Buckster已经在评论中解释的那样，您将vector<pii>而不是pii传递给bfs函数

这些只是编译问题。我不确定你的算法是否符合你的预期。您可以使用bfs来计算任意两个节点之间的距离，但是如果是加权的，bfs本身并不能给出最小路径。如果你对最小路径感兴趣，你可以使用Dijkstra，只要权重是正的。这里我有一个bfs的实现，你可以检查一下，如果你想的话，但它比你在这里要做的稍微复杂一些。