Algorytm Kruskala
Z Wikipedii
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 |
| edytuj ten szablon |
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 |
[edytuj] Algorytm
- 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:
- Wybierz i usuń z S krawędź 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.
[edytuj] Implementacja i złożoność
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)).
[edytuj] Zobacz też
[edytuj] Linki zewnętrzne
- Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50
- Implementacja w języku C++ [1]
