树中心节点(距离感最小值)

Question

我的问题如下:

给定树(V,E),找到中心节点v,使得总和{w in V} [dist(v,w)]最小,其中dist(v,w)是从v到最短路径的边数到w.算法应该在O(n)时间内运行(n是树中节点的数量).

这里和这里的问题也要求中心节点,但不同地定义它.

我没有严格地完成这些步骤,但实际上我认为我的问题的解决方案应该类似于这个问题的解决方案.

但是,我决定我应该与社区分享我的问题,因为我花了一段时间导航到链接,但是直接回答了问题.

Answer 1

我想出了这个解决方案：

1）选择任意一个节点作为根r，形成一棵树。对于该树中的每个子树，计算子树中的节点数（叶子是单节点树）。

以这棵树为例

          1
        / | \
       2  3  4 
      / \     \
     5   6     7
        / \
       8   9      

结果将是

          9
        / | \
       5  1  2 
      / \     \
     1   3     1
        / \
       1   1    

2) 计算所选根的距离总和。例如，如果选择顶点 1 作为根，则距离总和为 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3）以深度优先搜索的方式遍历树。例如，从顶点 1 开始，我们遍历到顶点 4。我们观察到，对于 7 个节点 (1,2,3,5,6,8,9)，我们进一步增加了 1（将 7=9-2 添加到分数），对于其他 2 (4,7)，我们更接近 1（减去 2）。得出的距离总和等于 15+(9-2)-2 = 20。

假设接下来我们从4遍历到7。现在我们得到的距离总和等于 20+(9-1)-1 = 27（距离 8 个顶点更远，距离 1 个顶点更近）。

另一个例子，如果我们从 1 遍历到 2，我们得到的距离总和等于 15+(9-5)-5 = 14。顶点 2 实际上是这个例子的解。

这将是我的算法。