Przejdź do zawartości

Algorytm Kruskala

Z Wikipedii, wolnej encyklopedii
Algorytm Kruskala
Ilustracja
Wizualizacja Algorytmu Kruskala
Rodzaj

Wyznaczanie minimalnego drzewa rozpinającego

Struktura danych

graf

Złożoność
Czasowa

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

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

Algorytm

[edytuj | edytuj kod]
  • 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 | edytuj kod]

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 | edytuj kod]
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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

Dowód jest indukcyjny.

Zobacz też

[edytuj | edytuj kod]

Przypisy

[edytuj | edytuj kod]

Bibliografia

[edytuj | edytuj kod]

Linki zewnętrzne

[edytuj | edytuj kod]