加權邊緣樹的中心

我想給我的大學assignement..given一個連接樹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

端算法

這是一個正確的解決方案有沒有其他更有效率的？謝謝你...

來源

2013-11-26 bece

一種方法（不高效）是首先構建所有節點之間的成對距離的二維矩陣。在矩陣上獲取MiniMax總行或列的工作。 –

@Abhishek是的，我知道，但我正在尋找一個更有效的解決方案..我需要一個比O（n^2） – bece

更好的算法，以及代表* O（n^2）中的'n' *？ –

你的想法是正確的。你可以隨意選擇任何頂點作爲樹的根，然後在'後序'中遍歷樹。由於權重總是正數，因此您始終可以選擇兩個最長的「分支」並更新O（1）中每個節點的答案。請記住，您正在尋找'全球'最長的路徑（即直徑圖），而不是通過子樹根部的'本地'最長路徑。

如果您搜索「（加權）約旦中心（樹中）」，您可以找到更多信息。樹的最佳算法是O（N），所以漸近地說你的解決方案是最優的，因爲你只使用一棵樹的O（| V | + | E |）== O（| V |）。

來源

2013-11-27 15:53:00 ile

加權邊緣樹的中心

回答

相關問題