使用 BFS 查找图形树的直径中心？

Question

所以这个函数，biggest_dist，求一个图的直径（任务中给定的图总是一棵树）。

我想让它找到的是找到直径的中心，即到所有其他节点的最大距离最小的节点。

我"kinda"理解我们可以通过找到从u到t的路径来做到这一点（u和t之间的距离是直径）通过跟踪每个节点的父节点。从那里我选择 u 和 t 中间的节点？我的问题是我如何在这里为这个功能实现它？这会使其成为该图的输出节点 2 吗？

int biggest_dist(int n, int v, const vector< vector<int> >& graph)
//n are amount of nodes, v is an arbitrary vertex
{ //This function finds the diameter of thegraph
int INF = 2 * graph.size(); // Bigger than any other length
vector<int> dist(n, INF);

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;
}

Answer 1

事实上，这个函数并不计算直径。它计算距离给定顶点 v.

最远的顶点

要计算一棵树的直径，首先需要选择一个任意顶点（假设v），然后找到离v最远的顶点（假设w)，然后找一个距离w最远的顶点，让我们坐u。 w 和 u 之间的距离是树的直径，但是 v 和 w 之间的距离（你的函数在做什么）不保证是直径.

为了让您的函数计算直径，您需要将它 return 设为它在距离旁边找到的顶点。方便的是，它始终是您处理的最后一个元素，因此只需让您的函数记住它处理的最后一个元素以及到该元素的距离，并且 return 它们都是。然后调用你的函数两次，首先从任意顶点，然后从第一个调用的顶点 returned.

为了让它真正找到中心，您还可以在 BFS 期间记住每个节点的父节点。为此，分配一个额外的数组，比如 prev，当你这样做时

dist[nghbr] = dist[pos] + 1;

也做

prev[nghbr] = pos;

然后在第二次调用该函数的末尾，您可以将 bdist/2 次下降到上一个，例如：

center = lastVertex;
for (int i = 0; i + i < bdist; ++ i) center = prev[center];

因此，对您的函数进行一些微调（使其 return 成为距离 v 最远的顶点和位于该路径中间的顶点，而不是 return直径），这段代码可能 return 你是树的中心（我只在你的例子中测试过，所以它可能有一些偏差）

pair<int, int> biggest_dist(int n, int v, const vector< vector<int> >& graph)
{
    int INF = 2 * graph.size(); // Bigger than any other length
    vector<int> dist(n, INF);
    vector<int> prev(n, INF);

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

    int bdist = 0; //biggest distance
    int lastV = v;
    while (!next.empty()) {
        int pos = next.front();
        next.pop();
        bdist = dist[pos];
        lastV = 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;
                prev[nghbr] = pos;
                next.push(nghbr);
            }
        }
    }

    int center = lastV;
    for (int i = 0; i + i < bdist; ++ i) center = prev[center];

    return make_pair(lastV, center);
}

int getCenter(int n, const vector< vector<int> >& graph)
{
    // first call is to get the vertex that is furthest away from vertex 0, where 0 is just an arbitrary vertes
    pair<int, int> firstResult = biggest_dist(n, 0, graph);
    // second call is to find the vertex that is furthest away from the vertex just found
    pair<int, int> secondResult = biggest_dist(n, firstResult.first, graph);
    return secondResult.second;
}

使用 BFS 查找图形树的直径中心？

Finding the center of the diameter of a graphtree using BFS?

graph

breadth-first-search