Wykonuję swoje badania i utknąłem z pytaniem:
Mam minimalne drzewo rozpinające (algorytm pierwotny), teraz jeden węzeł w moim drzewie zostaje usunięty, zastanawiam się, czy istnieje sposób, w jaki mogę ponownie zorganizować moje drzewo tak, że optymalność nadal się utrzymuje?
Szukam tu pewnych sugestii i docenię twoją pomoc.
Dziękuję Ci!
Odpowiedzi:
2 dla odpowiedzi № 1Ten problem został dobrze zbadany. Badania przeprowadzone w 2001 r. Znalazły sposób na utrzymanie struktury danych wykresu, dzięki czemu można wstawić lub usunąć krawędź i zaktualizować minimalne drzewo rozpinające w czasie O (log4 n), która według mojej najlepszej wiedzy jest najlepszazwiązany z czasem każdy był w stanie wymyślić jak dotąd. Artykuł opisujący ten algorytm jest gęsty i skomplikowany, ale jeśli jesteś zainteresowany, możesz go znaleźć tutaj:
Mam nadzieję że to pomoże!
1 dla odpowiedzi nr 2
Po usunięciu węzła z drzewa może się on podzielićwykres na więcej niż jeden odłączony komponent. W najgorszym przypadku wyobraź sobie MST, gdzie wszystkie krawędzie przechodzą z jednego centralnego węzła do wszystkich innych - jak gwiazda. W takim przypadku, jeśli węzeł centralny zostanie usunięty, cały MST będzie musiał zostać ponownie wykonany. Tak więc myślę, że krótka odpowiedź - zależy od tego, który węzeł jest usunięty. Rozwiązaniem jest zrobić to jak wspomniany aix - znajdź wszystkie komponenty, które są odłączone z powodu usuniętego węzła i połącz je łapczywie. Może to rozciągać się od 0 (jeśli usunie się węzeł liścia) do n-1 (jeśli środek gwiazdy zostanie usunięty)
-1 dla odpowiedzi nr 3
Jeśli usunięty wierzchołek był liściem MST, nie musisz nic robić: wciąż masz rozpinające się drzewo i nadal jest ono optymalne.
Jeśli nie był to liść, masz teraz dwa drzewa podrzędne. Wszystko, co musisz zrobić, to ponownie połączyć je za pomocą najkrótszej krawędzi, która istnieje między dwoma sub-drzewami. Najlepszym sposobem na znalezienie tej krawędzi jest prawdopodobnie użycie dowolnej struktury danych użytej dla algorytmu Prim (lub, trywialnie, w O (n ^ 2) przez rozważenie wszystkich par wierzchołków).