Algorytm Kruskala

134 jpg' alt='Algorytm_Kruskala'>
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.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)).