algorithm - 具有加权边缘的树的中心

Question

我正在尝试为我的大学作业提供一个解决方案..给定一个连通树 T=(V,E)。每条边 e 都有一个特定的正成本 c..d(v,w) 是节点 v 和 w 之间的距离..我被要求给出一个算法的伪代码，该算法找到这样一棵树的中心(该节点最小化到每个其他节点的最大距离)..

我的解决方案首先是找到树的前两个较高的分支..然后中心将位于较高的分支中，距根部的距离为 H/2(H 是树的高度之间的差值)两个更高的分支)..伪代码是:

Algorithm solution(Node root, int height, List path)
root: the root of the tree
height : the height measured for every branch. Initially height=0
path : the path from the root to a leaf. Initially path={root}

Result : the center of the tree

if root==null than
    return "error message"
endif

/*a list that will contain an element <h,path> for every
  leaf of the tree. h is the distanze of the leaf from the root
  and path is the path*/
List L = empty
if isLeaf(root) than
    L = L union {<height,path>}
endif

foreach child c of root do
    solution(c,height+d(root,c),path UNION {c})
endfor

/*for every leaf in the tree I have stored in L an element containing 
the distance from the root and the relative path. Now I'm going to pick
the two most taller branches of the tree*/
Array array = sort(L)
<h1,path1> = array[0]//corresponding to the tallest branch
<h2,path2> = array[1]//corresponding to the next tallest branch
H = h1 - h2;

/*The center will be the node c in path1 with d(root,c)=H/2. If such a 
node does not exist we can choose the node with te distance from the root
closer to H/2 */

int accumulator = 0
for each element a in path1 do
    if d(root,a)>H/2 than
        return MIN([d(root,a)-H/2],[H/2-d(root,a.parent)])
    endif   
end for

结束算法

这是一个正确的解决方案吗？是否有替代且更有效的解决方案？ 谢谢...

Answer 1

你的想法是正确的。您可以任意选择任何顶点作为树的根，然后以“后序”方式遍历树。由于权重始终为正，因此您始终可以选择两个最长的“分支”并以 O(1) 的时间更新每个节点的答案。 请记住，您正在寻找“全局”最长路径(即图形的直径)，而不是穿过子树根部的“局部”最长路径。

如果您搜索“(加权)乔丹中心(在树上)”，您可以找到更多信息。对于树来说，最佳算法是 O(N)，因此渐近地你的解决方案是最佳的，因为你只使用单个 DFS，对于树来说，它是 O(|V| + |E|) == O(|V|) 。