C++ : BFS to calculate distance between every pair of nodes in a tree

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.first，假设这些对具有意义(从，到)
• if(vis[ adj[ p ][ i ].first ] == false) :我假设您想检查邻居是否尚未访问。所以它应该更像这样:vis[adj[p.first][i].second] == false . visited 的索引是 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，前提是权重为正。 Here我有一个 bfs 实现，如果需要，您可以检查它，但它比您在这里尝试做的事情稍微复杂一些。