Outils :Vous avez un site web ? Un blog ?
 Technorati reactions rencontre |
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.
Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku.
Spis treści |
Po zakończeniu algorytmu L jest minimalnym drzewem rozpinającym.
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(ElogE) = O(ElogV) (ponieważ E < V2, zatem logE < 2logV).
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α(E,V)), gdzie α jest niezwykle wolno rosnącą funkcją (odwrotnością funkcji Ackermanna).
Całkowity czas działania jest zatem O(ElogV), 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α(E,V)).
