2

我正在尝试为我的大学作业提供一个解决方案..给定一个连接的树 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

结束算法

这是一个正确的解决方案吗？有没有其他更有效的解决方案？谢谢...

4

1 回答 1

2

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

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

于 2013-11-27T15:53:00.433 回答