Algorytm Kruskala

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Algorytm 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 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].

Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku[potrzebne źródło].

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

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]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.

Linki zewnętrzne[edytuj | edytuj kod]