Znajdź wszystkie krytyczne krawędzie MST

Question

Mam to pytanie z książki Roberta Sedgewicka na temat algorytmów.

Krytyczne krawędzie. Krawędź MST, której usunięcie z wykresu spowodowałoby zwiększenie masy MST o , nazywa się krawędzią krytyczną. Pokaż, jak znaleźć wszystkie krytyczne krawędzie wykresu w czasie proporcjonalnym do E log E. Uwaga: To pytanie zakłada, że ​​grubości krawędzi niekoniecznie są odrębne (w przeciwnym razie wszystkie krawędzie w MST są krytyczne).

Proszę zasugerować algorytm, który rozwiąże ten problem.

Jedno podejście, jakie mogę wymyślić, działa w czasie E.V. Moje podejście polega na uruchomieniu algorytmu kruskala.

Ale za każdym razem, gdy napotykamy krawędź, której wstawienie w MST tworzy cykl i jeśli ten cykl już zawiera krawędź o tej samej wadze krawędziowej, wówczas wstawiona krawędź nie będzie krawędzią krytyczną (w przeciwnym razie wszystkie pozostałe MST krawędzie są krytycznymi krawędziami).

Czy ten algorytm jest poprawny? Jak mogę rozszerzyć ten algorytm, aby wykonać zadanie w czasie E log E.

Answer 1

Tak, Twój algorytm jest poprawny. Możemy to udowodnić, porównując wykonanie algorytmu Kruskala z podobnym wykonaniem, w którym koszt pewnej krawędzi MST e zmienia się w nieskończoność. Do czasu pierwszej realizacji e, obie egzekucje są identyczne. Po e, pierwsze wykonanie ma jeden mniej połączony komponent niż drugi. Ten stan utrzymuje się do momentu, gdy krawędź e 'zostanie uznana, że ​​w drugim wykonaniu łączy elementy, które miałby. Ponieważ edge e jest jedyną różnicą między lasami zbudowanymi do tej pory, musi należeć do cyklu stworzonego przez e '. Po e 'egzekucje podejmują identyczne decyzje, a różnica w lasach polega na tym, że pierwsze wykonanie ma e, a drugie, e'.

Jednym ze sposobów wdrożenia tego algorytmu jest użycie drzewa dynamicznego, struktury danych reprezentującej etykietowany las. Jedna konfiguracja tego narzędzia ADT obsługuje następujące metody w czasie logarytmicznym .

• MakeVertex() - konstruuje i zwraca świeży wierzchołek.
• Łącze (u, c, v) - wierzchołki u i v nie mogą być połączone. Tworzy nieoznakowaną krawędź od wierzchołka u do wierzchołka v z kosztem c.
• Znak (u, v) - wierzchołki u i v muszą być punktami końcowymi krawędzi e. Znaki e.
• Połączony (u, v) - wskazuje, czy wierzchołki u i v są połączone.
• FindMax (u, v) - wierzchołki u i v muszą być połączone. Zwraca punkty końcowe nieoznakowanej krawędzi na unikalnej ścieżce od u do v z maksymalnym kosztem, wraz z tym kosztem. Punkty końcowe tej krawędzi podane są w kolejności, w jakiej pojawiają się na ścieżce.

Nie twierdzę, że jest to dobry algorytm w praktyce. Dynamiczne drzewa, takie jak szwajcarskie noże armii, są wszechstronne, ale skomplikowane i często nie są najlepszym narzędziem do tego zadania. Zachęcam do zastanowienia się, jak wykorzystać fakt, że możemy poczekać, aż wszystkie krawędzie zostaną przetworzone, aby dowiedzieć się, jakie są krytyczne krawędzie.

Answer 2

Stan, który sugerujesz, gdy krawędź jest krytyczna, jest prawidłowy, tak myślę.Ale nie jest konieczne, aby znaleźć cykl i przetestować każdy jego brzeg.

Algorytm Kruskala dodaje krawędzie w rosnącej kolejności, więc kolejność dodawania krawędzi może zostać podzielona na bloki o równych krawędziach. Wewnątrz każdego bloku o równej wadze, jeśli istnieje więcej niż jedna krawędź łącząca te same dwa składniki, wszystkie te krawędzie są niekrytyczne, ponieważ zamiast tego można wybrać dowolną z pozostałych krawędzi. (Mówię, że nie są one krytyczne, ponieważ w rzeczywistości nie otrzymujemy konkretnego MST jako części danych wejściowych - gdybyśmy wtedy byli, to określilibyśmy konkretną krawędź, by wywołać niekrytyczne krawędź, którą faktycznie wybiera Kruskal, tylko artefakt początkowego porządkowania krawędzi lub sposobu zaimplementowania sortowania.)

Ale to nie jest wystarczające: może być tak, że po dodaniu wszystkich krawędzi wagi 4 lub mniejszej do MST, okazuje się, że istnieją 3 5 krawędzi, łączących pary elementów (1, 2), (2, 3) i (1, 3). Chociaż żadna para komponentów nie jest połączona przez więcej niż 1 z tych 3 krawędzi, potrzebujemy tylko (dowolnych) 2 z nich - użycie wszystkich 3 spowoduje utworzenie cyklu.

Dla każdego bloku o jednakowej wadze, mając wagę np. W, musimy faktycznie (teoretycznie) utworzyć nowy wykres, w którym każdy składnik MST do tej pory (tj. Przy użyciu krawędzi o wadze < w) jest wierzchołku, a między dwoma wierzchołkami znajduje się krawędź, gdy między tymi komponentami znajduje się granica waga. (Może to skutkować wieloma krawędziami.) Następnie uruchomimy DFS na każdym komponencie tego wykresu, aby znaleźć dowolne cykle i oznaczyć wszystkie krawędzie należące do takiego cyklu jako niekrytyczne. DFS pobiera czas O (nEdges), więc suma czasów DFS dla każdego bloku (którego rozmiary sumują się do E) będzie wynosić O (E).

Zauważ, że algorytm Kruskala wymaga czasu O (Elog E), a nie O (E), jak sugerujesz - chociaż ludzie tacy jak Bernard Chazelle zbliżają się do linearnej konstrukcji MST, TTBOMK, której jeszcze nikt nie ma ! :)