Algorytm Kruskala
Algorytm Kruskala – algorytm grafowy wyznaczający minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny[1]. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa[2]. Jest to przykład algorytmu zachłannego[2].
 Wizualizacja Algorytmu Kruskala | |
| Rodzaj |
Wyznaczanie minimalnego drzewa rozpinającego |
|---|---|
| Struktura danych | |
| Złożoność | |
| Czasowa |
|
Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku w czasopiśmie Proceedings of the American Mathematical Society[3].
Algorytm edytuj
- Utwórz las L z wierzchołków oryginalnego grafu – każdy wierzchołek jest na początku osobnym drzewem.
- Utwórz zbiór S zawierający wszystkie krawędzie oryginalnego grafu.
- Dopóki S nie jest pusty oraz L nie jest jeszcze drzewem rozpinającym:
- Wybierz i usuń z S jedną z krawędzi o minimalnej wadze.
- Jeśli krawędź ta łączyła dwa różne drzewa, to dodaj ją do lasu L, tak aby połączyła dwa odpowiadające drzewa w jedno.
- W przeciwnym wypadku odrzuć ją.
Po zakończeniu algorytmu L jest minimalnym drzewem rozpinającym.
Implementacja i złożoność edytuj
Jako zbiór E można wziąć tablicę wszystkich krawędzi posortowaną według wag. Wtedy w każdym kroku najmniejsza krawędź to po prostu następna w kolejności. Sortowanie działa w czasie (ponieważ zatem ).
Drugą fazę algorytmu można zrealizować przy pomocy struktury zbiorów rozłącznych – na początku każdy wierzchołek tworzy osobny zbiór, struktura pozwala na sprawdzenie, czy dwa wierzchołki są w jednym zbiorze i ewentualne połączenie dwu zbiorów w jeden. Przy implementacji przez tzw. las drzew rozłącznych z kompresją ścieżki operacje te łącznie działają w czasie gdzie jest niezwykle wolno rosnącą funkcją (odwrotnością funkcji Ackermanna).
Całkowity czas działania jest zatem ze względu na pierwszą fazę – sortowanie. Jeśli wagi krawędzi są już na wejściu posortowane, albo pozwalają na użycie szybszych algorytmów sortowania (na przykład sortowania przez zliczanie), algorytm działa w czasie
Przykład edytuj
| Ilustracja | Opis |
|---|---|
|
AD i CE to najkrótsze krawędzie (o długości 5). Losowo została wybrana krawędź AD. |
|
Najkrótszą niewybraną jeszcze krawędzią jest teraz CE, więc zostaje wybrana. |
|
Na tej samej zasadzie zostaje wybrana krawędź DF. |
|
Najkrótsze krawędzie to teraz AB i BE, o długościach 7. Krawędź AB zostaje wybrana losowo i zaznaczona. Krawędź BD natomiast, została oznaczona kolorem czerwonym, ponieważ istnieje już ścieżka po której można by przejść od B do D. Innymi słowy, nie powinna zostać nigdy wybrana, żeby uniknąć powstania cyklu ABDA. |
|
Zostaje wybrana najkrótsza, niewybrana jeszcze krawędź – BE. 3 inne krawędzie zostają oznaczone kolorem czerwonym: BC, bo jej wybór oznaczałby powstanie cyklu BCEB, DE żeby uniknąć cyklu DEBAD i FE, żeby uniknąć cyklu FEBADF. |
|
Proces postępuje analogicznie i powstaje minimalne drzewo rozpinające (wszystkie wierzchołki są połączone). |
Dowód poprawności edytuj
Dowód podzielony jest na dwie części. Najpierw dowodzimy, że graf generowany przez algorytm jest drzewem rozpinającym, a następnie że jest to drzewo o najmniejszej wadze.
Drzewo rozpinające edytuj
Niech będzie spójnym, ważonym grafem oraz niech będzie podgrafem wygenerowanym przez algorytm. nie może zawierać cyklu, ponieważ dodana krawędź która miałaby tworzyć cykl musiałaby zostać dodana do drzewa, które jest podgrafem, a nie połączyć dwa drzewa, co jest niezgodne z algorytmem. nie może być niespójny, ponieważ pierwsza napotkana krawędź (tzn. ta o najmniejszej wadze) łącząca te składowe zostałaby wybrana przez algorytm (jej istnienie wynika z założenia, że wyjściowy graf jest spójny). Stąd jest drzewem rozpinającym
Minimalna waga edytuj
Dowód jest indukcyjny.
Zobacz też edytuj
Przypisy edytuj
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 568–569.
- ↑ a b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 569.
- ↑ Joseph B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. „Proceedings of the American Mathematical Society”. 7 (1), s. 48–50, 1956. DOI: 10.1090/S0002-9939-1956-0078686-7. ISSN 0002-9939. [dostęp 2015-06-24].
Bibliografia edytuj
- Thomas H. Cormen, Charles Eric Leiserson, Ronald Linn Rivest, Clifford Stein: Wprowadzenie do algorytmów. Krzysztof Diks (tłum.). Wyd. 8. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, seria: Klasyka Informatyki. ISBN 978-832043328-9. OCLC 749241843. (pol.).
Linki zewnętrzne edytuj
- Rafał Nowak: Implementacja Algorytmu Kruskala w języku C++. rafalnowak.pl, 2008-02-27. [dostęp 2015-06-24]. [zarchiwizowane z tego adresu (2015-06-24)]. (pol.).