使用 BFS 查找与图中所有其他节点的最大距离最小的节点？

Question

几天前我做了这个函数来使用 BFS 求出图形的直径：

dist[v] = 0;
queue<int> next;
next.push(v);

int bdist = 0; //biggest distance
while(!next.empty()) {
    int pos = next.front();
    next.pop();
    bdist = dist[pos];

    for(int i = 0; i < graph[pos].size(); ++i) {
        int nghbr = graph[pos][i];
        if(dist[nghbr] > dist[pos]+1) {
            dist[nghbr] = dist[pos]+1;
            next.push(nghbr);
        }
    }
}

return bdist-1;
}

How/what 我是否更改代码以便返回与所有其他节点的最大距离最小的节点，而不是返回直径？新代码会是什么样子？

Answer 1

基本上你是在为每个节点调用函数biggest_dist（另外我猜你应该return bdist 而不是bdist-1）。因此，对于每个节点，您都可以获得最大节点与该节点的距离。所以这是获取具有最小最大距离的节点的伪代码

     /*g is your graph */
     /* This code goes in your main */
     /* assuming 0 based indexing of nodes */
     answer = 0 /* stores your answer, let node 0 be the answer we will update it */
     dis    = biggest_dist(0,g) /* stores the maximum distances of node 0 */
     for each node 
           maxdist = biggest_dist(node,g)
           if maxdist < dis:
              dis = maxdist
              answer = node

     print answer /* your answer */

请记住可以有多个答案，这将打印其中的任何一个。同样按照其他人的建议，您应该编辑您的问题以反映您的努力。
编辑
该算法的复杂度为O(EV+V^2)。如果您使用 floyyd warshall 来计算您可以轻松获得答案的所有对象之间的最短距离，它将是 O(V^3) 并使用 dijakstra 的值为 O(EV+V^2logV)。现在在一个简单的图表中 E 最多可以是 V^2 如果我必须降低时间复杂度，我会选择你给出的算法。

使用 BFS 查找与图中所有其他节点的最大距离最小的节点？

Finding which node that has the least maximum distance to all the other nodes in a graph using BFS?

graph

breadth-first-search

data-structures