Algorytm Borůvki - Borůvka's algorithm
Algorytm Borůvki to zachłanny algorytm do znajdowania minimalnego drzewa opinającego w grafie lub minimalnego lasu opinającego w przypadku grafu, który nie jest połączony.
Po raz pierwszy została opublikowana w 1926 r. przez Otakara Borůvkę jako metoda budowy wydajnej sieci elektrycznej dla Moraw . Algorytm został ponownie odkryty przez Choqueta w 1938 roku; ponownie przez Florka , Łukasiewicza , Perkala , Steinhausa i Zubrzyckiego w 1951; i ponownie przez Georgesa Sollina w 1965. Algorytm ten jest często nazywany algorytmem Sollina , zwłaszcza w literaturze dotyczącej obliczeń równoległych .
Algorytm rozpoczyna się od znalezienia krawędzi o minimalnej wadze przypadającej na każdy wierzchołek grafu i dodania wszystkich tych krawędzi do lasu. Następnie powtarza podobny proces znajdowania krawędzi o minimalnej wadze z każdego skonstruowanego do tej pory drzewa do innego drzewa i dodawania wszystkich tych krawędzi do lasu. Każde powtórzenie tego procesu zmniejsza liczbę drzew w każdym połączonym elemencie grafu do co najwyżej połowy tej poprzedniej wartości, więc po logarytmicznie wielu powtórzeniach proces się kończy. Kiedy tak się dzieje, zestaw krawędzi, które dodała, tworzy minimalny las opinający.
Pseudo kod
Poniższy pseudokod ilustruje podstawową implementację algorytmu Borůvki. W klauzulach warunkowych każda krawędź uv jest uważana za tańszą niż „Brak”. Celem uzupełnionej zmiennej jest określenie, czy las F jest jeszcze lasem obejmującym.
Jeśli krawędzie nie mają wyraźnych wag, należy zastosować spójną regułę rozstrzygania remisów , np. w oparciu o pewną całkowitą kolejność wierzchołków lub krawędzi. Można to osiągnąć, reprezentując wierzchołki jako liczby całkowite i porównując je bezpośrednio; porównywanie ich adresów pamięci ; itp. Reguła rozstrzygania remisów jest konieczna, aby upewnić się, że utworzony graf rzeczywiście jest lasem, to znaczy nie zawiera cykli. Rozważmy na przykład wykres trójkątny z węzłami { a , b , c } i wszystkimi krawędziami wagi 1. Wtedy cykl mógłby zostać utworzony, jeśli wybierzemy ab jako minimalną krawędź wagi dla { a }, bc dla { b } i ca dla { c }. Reguła rozstrzygająca, która porządkuje krawędzie najpierw według źródła, a następnie według celu, zapobiegnie tworzeniu cyklu, co skutkuje minimalnym drzewem opinającym { ab , bc }.
algorithm Borůvka is input: A weighted undirected graph G = (V, E). output: F, a minimum spanning forest of G. Initialize a forest F to (V, E') where E' = {}. completed := false while not completed do Find the connected components of F and assign to each vertex its component Initialize the cheapest edge for each component to "None" for each edge uv in E, where u and v are in different components of F: let wx be the cheapest edge for the component of u if is-preferred-over(uv, wx) then Set uv as the cheapest edge for the component of u let yz be the cheapest edge for the component of v if is-preferred-over(uv, yz) then Set uv as the cheapest edge for the component of v if all components have cheapest edge set to "None" then // no more trees can be merged -- we are finished completed := true else completed := false for each component whose cheapest edge is not "None" do Add its cheapest edge to E' function is-preferred-over(edge1, edge2) is return (edge1 is "None") or (weight(edge1) < weight(edge2)) or (weight(edge1) = weight(edge2) and tie-breaking-rule(edge1, edge2)) function tie-breaking-rule(edge1, edge2) is The tie-breaking rule; returns true if and only if edge1 is preferred over edge2 in the case of a tie.
Jako optymalizację można by usunąć z G każdą znalezioną krawędź łączącą dwa wierzchołki w tym samym komponencie, tak aby nie przyczyniała się do czasu poszukiwania najtańszych krawędzi w późniejszych składowych.
Złożoność
Można pokazać, że algorytm Borůvki wykonuje O (log V ) iteracji zewnętrznej pętli aż do jej zakończenia, a zatem działa w czasie O ( E log V ), gdzie E jest liczbą krawędzi, a V jest liczbą wierzchołków w G (zakładając E ≥ V ). W grafach planarnych , a bardziej ogólnie w rodzinach grafów zamkniętych w ramach mniejszych operacji grafu , można go uruchomić w czasie liniowym, usuwając wszystkie, oprócz najtańszej krawędzi, między każdą parą składowych po każdym etapie algorytmu.
Przykład
Inne algorytmy
Inne algorytmy rozwiązania tego problemu to algorytm Prima i algorytm Kruskala . Szybkie algorytmy równoległe można uzyskać, łącząc algorytm Prima z algorytmem Borůvki.
Szybszy randomizowany algorytm minimalnego drzewa opinającego oparty częściowo na algorytmie Borůvki ze względu na Kargera, Kleina i Tarjana działa w oczekiwanym czasie O( E ) . Najbardziej znany (deterministyczny) algorytm minimalnego drzewa opinającego autorstwa Bernarda Chazelle'a również opiera się częściowo na algorytmie Borůvki i działa w czasie O( E α ( E , V ) ) , gdzie α jest odwrotnością funkcji Ackermanna . Te randomizowane i deterministyczne algorytmy łączą kroki algorytmu Borůvki, zmniejszając liczbę elementów, które pozostają do połączenia, z krokami innego typu, które zmniejszają liczbę krawędzi między parami elementów.
Uwagi
- ^ Borůvka, Otakar (1926). "O jistém problému minimálním" [O pewnym minimalnym problemie]. Pracę Mor. Přírodověd. Sp. V Brně III (w języku czeskim i niemieckim). 3 : 37–58.
- ^ Borůvka, Otakar (1926). „Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Wkład w rozwiązanie problemu ekonomicznej budowy sieci elektrycznych)”. Elektronický Obzor (po czesku). 15 : 153-154.
- ^ Nešetřil, Jaroslav ; Milková, Ewa; Nešetřilová, Helena (2001). „Otakar Borůvka o problemie minimalnego drzewa opinającego: tłumaczenie obu artykułów z 1926 r., komentarze, historia”. Matematyka dyskretna . 233 (1–3): 3-36. doi : 10.1016/S0012-365X(00)00224-7 . hdl : 10338.dmlcz/500413 . MR 1825599 .
- ^ Choquet, Gustave (1938). „Étude de somes réseaux de route”. Comptes Rendus de l'Académie des Sciences (w języku francuskim). 206 : 310-313.
- ^ Florek K.; Łukaszewicz, J. ; Perkal, J.; Steinhaus, Hugo ; Zubrzycki S. (1951). „Sur la liaison et la Division des points d'un ensemble fini” . Colloquium Mathematicae (w języku francuskim). 2 : 282–285. MR 0048832 .
- ^ Sollin, Georges (1965). „Le tracé de kanalizacji”. Programowanie, gry i sieci transportowe (w języku francuskim).
- ^ Eppstein, Dawid (1999). „Drzewa napinające i klucze”. W Sack, J.-R. ; Urrutia, J. (red.). Podręcznik geometrii obliczeniowej . Elsevier. s. 425-461.; Mareš, Martin (2004). „Dwa algorytmy czasu liniowego dla MST na mniejszych klasach grafów zamkniętych” (PDF) . Archiwum Matematyczne . 40 (3): 315-320..
- ^ Bader, David A.; Cong, Guojing (2006). „Szybkie algorytmy pamięci współdzielonej do obliczania minimalnego lasu rozpiętości grafów”. Journal of Parallel and Distributed Computing . 66 (11): 1366–1378. CiteSeerX 10.1.1.129.8991 . doi : 10.1016/j.jpdc.2006.06.001 .
- ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). „Algorytm randomizowanego czasu liniowego, aby znaleźć minimalne drzewa opinające”. Dziennik ACM . 42 (2): 321–328. CiteSeerX 10.1.1.39.9012 . doi : 10.1145/201019.201022 .
- ^ Chazelle Bernard (2000). „Algorytm minimalnego drzewa opinającego o złożoności typu odwrotnego Ackermanna” (PDF) . J. ACM . 47 (6): 1028–1047. CiteSeerX 10.1.1.1115.2318 . doi : 10.1145/355541.355562 .