Wyszukiwanie drzewa opinającego, które minimalizuje sumę głębokości węzłów.

Question

Mam nieskoordynowany połączony wykres z nieważonymi krawędziami. Jak zbudować drzewo opinające (rozwiązanie może nie być unikalne), tak aby zminimalizować sumę głębokości wszystkich węzłów? Nie jest to oczywiście znalezienie minimalnego drzewa opinającego, ponieważ "waga" krawędzi faktycznie różni się w zależności od głębokości dziecka.

Myślę, że biorąc pod uwagę wyznaczony katalog główny, drzewo z minimalną sumą głębokości może zostać utworzone przez chciwie łączące wszystko, co można połączyć jako potomstwo, z każdym węzłem w kolejności wszerz. Dlatego zamierzam znaleźć drzewo o minimalnej całkowitej głębokości, stosując tę ​​samą procedurę N razy, wyznaczając każdy z N węzłów jako root i wybierając minimalną spośród N kandydatów. Czy to jest prawidłowy algorytm? Proszę wskazać, czy jest źle, lub czy istnieje coś bardziej wydajnego.

Answer 1

Czy jest to prawidłowy algorytm?

Tak, algorytm jest poprawny.

Biorąc węzeł R to uznać korzeniem drzewa rozpinającego, głębokość węzła N w drzewie obejmującym co najmniej długość najkrótszej ścieżki od R do N na wykresie, więc suma głębokości jest co najmniej sumą długości najkrótszych ścieżek (od R).

Drzewo zbudowane przez algorytm łączy każdy węzeł z R z jedną z najkrótszych ścieżek, więc suma głębokości jest sumą odległości, które widzieliśmy powyżej, jest dolną granicą.

Jako mała optymalizacja, jeśli liczba węzłów wynosi co najmniej 3, żadne węzły o stopniu 1 nie powinny być uważane za główny element drzewa. (W przypadku drzewa zakorzenionego w węźle R ze stopniem 1 uwzględnij ten sam wykres, widzianego jako drzewo zakorzenione na sąsiadzie R. Głębokość R zwiększa się o 1, głębokość wszystkich innych węzłów zmniejsza się o 1, więc suma głębokości zmniejsza się o number_of_nodes - 2.)