algorithm - 寻找树的中心

Question

我有一个问题，这是我计划的一部分。

对于 T=(V,E) 树，我们需要在树中找到节点 v，使从 v 到任何其他节点的最长路径的长度最小化。

那么我们如何找到树的中心呢？是否只能有一个或多个中心？

如果有人可以为此提供好的算法，那么我可以了解如何适应我的程序。

Answer 1

有两种方法可以做到这一点(两者同时运行):

• 使用 BFS(我将在此处描述)
• 使用FIFO queue .

---

选择树上的任何顶点 v1。运行 BFS从这个顶点。您将继续的最后一个顶点 (v2) 将是距 v1 最远的顶点。现在运行另一个 BFS，这次从顶点 v2 获取最后一个顶点 v3。

从 v2 到 v3 的路径是树的直径，您的中心位于树的某处。更准确地说，它位于它的中间。如果路径有 2n + 1 个点，则只有 1 个中心(在 n + 1 的位置)。如果路径有 2n 个点，则在 n 和 n + 1 位置将有两个中心。

您只使用 2 个 BFS 调用，运行时间为 2 * O(V)。