c++ - 请提出一些算法来找到树中所有节点中到最远节点的距离最小的节点

Question

请提出一些算法来找到树中所有节点中到最远节点的距离最小的节点。

它不是图表，也没有加权。

Answer 1

在树 T 中选择一个任意节点 v。运行 BFS，使 v 作为 T 的根。BFS 输出从 v 到 T 所有其他节点的距离。

现在选择一个距离 v 最远的节点 u。再次运行 BFS，使 u 成为根。在新的距离输出上，找到距离 u 最远的节点 w。

考虑u 和w 之间的路径。这是 T 树中最长的路径。路径中间的节点是 T 树的中心。

请注意，树中可能存在两个中心。如果是这样，他们就是邻居。

性能:O(n)，其中n是T的节点数。

证明

声明:距离some节点v最远的叶子(u)位于最长的路径上.

如果我们证明了这一点，那么该算法是正确的，因为它首先找到 u，并且因为它是最长路径的一端，所以使用 DFS 自己找到这条路径。

声明的证明:让我们使用 retucto ad absurdum。假设 u---r 是树中最长的路径；对于某些节点v，v---u和v---r都不是从v 。相反，最长的路径是 v---k。我们有两种情况:

a) u---r 和 v--k 有一个公共(public)节点 o。然后 v--o--u 和 v--o--r 比 u---o---k 短。然后 o---r 比 o---k 短。那么 u---o---r 不是图中最长的路径，因为 u---o---k 更长。这与我们的假设相矛盾。

b) u---r 和 v--k 没有公共(public)节点。但是由于图是连通的，在每条路径上都有节点 o1 和 o2，使得它们之间的路径 o1--o2在这两条路径上不包含任何其他节点。与假设的矛盾与 a) 点相同，但 o1--o2 而不是单纯的 o(事实上，a 只是 b 的一个特例，其中 o1=o2)。

这证明了声明，从而证明了算法的正确性。

(这是Pavel Shved写的证明，原作者可能有更短的证明)