加权边缘的树木的中心

问题描述

我试图给出一个解决方案，我的大学assignement..given连树T =（V，E）。每个边e具有特定的正成本c..d（V，W）是要求给一个算法的伪code表示找到这样的树木的中心节点V和w..I'm之间的距离（最小化的最大距离的每一个其他节点的节点）..

i am trying to give a solution to my university assignement..given a connected tree T=(V,E). every edge e has a specific positive cost c..d(v,w) is the distance between node v and w..I'm asked to give the pseudocode of an algorithm that finds the center of such a tree(the node that minimizes the maximum distance to every other node)..

我的溶液首先在于找到的tree..then中心将在更高的分支中，从根部的距离的H / 2的前两个高分支（H是的高度之间的差2高枝）..伪code是：

My solution consists first of all in finding the first two taller branches of the tree..then the center will be in the taller branch in a distance of H/2 from the root(H is the difference between the heights of the two taller branches)..the pseudocode is:

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

结束算法

这是一个正确的解决方案？是否有另一种更高效的？谢谢你...

is this a correct solution??is there an alternative and more efficient one??Thank you...

推荐答案

你的想法是正确的。您可以随意挑选任何顶点是树的根，然后遍历后序的树。由于权重始终是积极的，你总能挑两个最长的分行'和更新（1）每个节点为O答案。只要记住，你正在寻找的全球最长的路径（即直径图表），而不是通过子树的根本地最长的路径。

Your idea is correct. You can arbitrarily pick any vertex to be a root of the tree, and then traverse the tree in 'post-order'. Since the weights are always positive, you can always pick the two longest 'branches' and update the answer in O(1) for each node.Just remember that you are looking for the 'global' longest path (i.e. diameter of the graph), rather than the 'local' longest paths that go through the roots of the subtrees.

您可以找到更多的信息，如果你搜索（加权）约旦中心（在树上）。最佳算法是O（N）的树木，所以渐进您的解决方案是最佳的，因为你只用一个单一的DFS是O（| V | + | E |）== O（| V |）。一棵树

You can find more information if you search for "(weighted) Jordan Center (in a tree)". The optimal algorithm is O(N) for trees, so asymptotically your solution is optimal since you only use a single DFS which is O(|V| + |E|) == O(|V|) for a tree.

这篇关于加权边缘的树木的中心的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！