Algorytm Kruskala

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Algorytm Kruskala
MST kruskal en.gif
Wizualizacja Algorytmu Kruskala
Rodzaj Wyznaczanie minimalnego drzewa rozpinającego
Struktura danych graf
Złożoność
Czasowa O(E \cdot \log V)
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


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 S 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 O(E log E) = O(E log V) (ponieważ E < V^2, zatem 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 O(E \alpha(E,V)), gdzie \alpha jest niezwykle wolno rosnącą funkcją (odwrotnością funkcji Ackermanna).

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

Przykład[edytuj | edytuj kod]

Ilustracja Opis
Kruskal Algorithm 1.svg AD i CE to najkrótsze krawędzie (o długości 5). Losowo została wybrana krawędź AD.
Kruskal Algorithm 2.svg Najkrótszą niewybraną jeszcze krawędzią jest teraz CE, więc zostaje wybrana.
Kruskal Algorithm 3.svg Na tej samej zasadzie zostaje wybrana krawędź DF.
Kruskal Algorithm 4.svg 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 ABD.
Kruskal Algorithm 5.svg 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 BCE, DE żeby uniknąć cyklu DEBA i FE, żeby uniknąć cyklu FEBAD.
Kruskal Algorithm 6.svg 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 G będzie spójnym, ważonym grafem oraz niech T będzie podgrafem wygenerowanym przez algorytm. 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. T nie może być niespólny, 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 T jest drzewem rozpinającym G.

Minimalna waga[edytuj | edytuj kod]

Dowód jest indukcyjny.

Zobacz też[edytuj | edytuj kod]

Przypisy

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]