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].

Algorytm Kruskala

Wizualizacja Algorytmu Kruskala
Rodzaj	Wyznaczanie minimalnego drzewa rozpinającego
Struktura danych	graf
Złożoność
Czasowa	${\displaystyle O(E\cdot \log V)}$

Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku w czasopiśmie Proceedings of the American Mathematical Society^[3].

Algorytm

• 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ść

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 ${\displaystyle O(E\log E)=O(E\log V)}$ (ponieważ ${\displaystyle E<V^{2},}$ zatem ${\displaystyle \log E<2\log V}$).

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 ${\displaystyle O(E\alpha (E,V)),}$ gdzie ${\displaystyle \alpha }$ jest niezwykle wolno rosnącą funkcją (odwrotnością funkcji Ackermanna).

Całkowity czas działania jest zatem ${\displaystyle O(E\log V),}$ 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 ${\displaystyle O(E\alpha (E,V)).}$

Przykład

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

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

Niech ${\displaystyle G}$ będzie spójnym, ważonym grafem oraz niech ${\displaystyle T}$ będzie podgrafem wygenerowanym przez algorytm. ${\displaystyle T}$ 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. ${\displaystyle T}$ 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 ${\displaystyle T}$ jest drzewem rozpinającym ${\displaystyle G.}$

Minimalna waga

Dowód jest indukcyjny.

Zobacz też

• algorytm Prima

Przypisy

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 568–569.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 569.
3. 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

• 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

• 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.).