相关疑难解决方法(0)

给定一棵树,如何在树中找到中心节点,使得从中心节点到其他节点的距离最小(假设每条边具有单位重量)？我正在尝试使用DFS但是可以在线性时间内完成吗？

我的问题如下:

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

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

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

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