algorithm - 树中的中心节点(距离最小和)

Question

我的问题如下:

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

问题here和 here也要求中心节点，但定义不同。

我没有严格执行这些步骤，但实际上我认为我的问题的解决方案应该与 this problem 的解决方案类似.

但是，我决定与社区分享我的问题，因为我花了一些时间才导航到 the link。 ，但这并没有直接回答问题。

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) 遍历 depth-first-search 中的树方式。例如，从顶点 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 实际上是这个例子的解。

这就是我的算法。