центр дерева с взвешенными ребрами

Question

Я пытаюсь дать решение моей университетской должности .. связанное дерево T = (V, E). каждое ребро e имеет определенную положительную стоимость c..d (v, w) - это расстояние между узлами v и w. Я попросил дать псевдокод алгоритма, который находит центр такого дерева (узел, который минимизирует максимальное расстояние до каждого другого узла).

Мое решение состоит в первую очередь в поиске первых двух более высоких ветвей дерева. Затем центр будет находиться в более высокой ветке на расстоянии H/2 от корень (Н представляет собой разность между высотами два высоких ветвей) .. псевдокодом является:

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 |) для дерева.