寻找树的中心

Question

我有一个问题,这是我的计划的一部分.

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

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

如果有人能为我提供良好的算法,那么我就可以了解如何融入我的计划.

Answer 1

考虑一个有两个节点的树？哪个是中心？任何一个都足够了,一棵树可以有一个以上的中心.

现在,想想成为中心意味着什么.如果所有分支都是相同的高度,则中心是根(所有路径都通过根).如果分支具有不同的高度,那么中心必须是根或在具有最大高度的分支中,否则最大路径大于最高分支的高度,并且根将是更好的选择.现在,我们需要看最高的分支到底有多远？最高分支(从根部)到下一个最高分支之间的高度差异的一半(如果差异最多为1根则足够).为什么,因为当我们沿着最高的分支向下移动一级时,我们将通向下一个最高分支的最深节点的路径延长一个,并将到当前分支中最深节点的距离减少一个.最终,当你穿过深度差异的一半时,它们将是平等的.现在,当我们走下最高的分支时,我们只需要在每个级别选择最高的子分支.如果多个具有相同的高度,我们只需任意选择一个.

基本上,您正在做的是找到图中最长的路径,即树的最高分支与下一个最高分支之间的距离,然后在该分支上找到中间节点.因为可能存在与最长路径长度相同的多条路径,并且最长路径的长度可能是均匀的,所以您有多个可能的中心.

Answer 2

有两种方法可以做到这一点（两种方法可以同时运行）：

• 使用BFS（我将在这里描述）
• 使用FIFO队列。

选择v1树上的任何顶点。从该顶点运行BFS。v2您要进行的最后一个顶点（）将是离的最远顶点v1。现在运行另一个BFS，这次是从顶点开始v2并获得最后一个顶点v3。

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

您只使用2个BFS调用，这些调用可以2 * O(V)及时运行。