Algorytm Kruskala

Algorytm Kruskala

Algorytm Kruskala to metoda wykorzystywana w teorii grafów, mająca na celu znalezienie minimalnego drzewa rozpinającego dla spójnego, nieskierowanego grafu ważonego. Oznacza to, że algorytm ten identyfikuje drzewo, które obejmuje wszystkie wierzchołki grafu, przy minimalnej możliwej wadze. Jest to przykład algorytmu zachłannego.

Po raz pierwszy algorytm został zaprezentowany przez Josepha Kruskala w 1956 roku w czasopiśmie Proceedings of the American Mathematical Society.

Algorytm

Na początku tworzymy las L z wierzchołków oryginalnego grafu, gdzie każdy wierzchołek stanowi oddzielne drzewo.

Tworzymy również zbiór S, który zawiera wszystkie krawędzie oryginalnego grafu.

Póki zbiór S nie jest pusty, a L nie stanowi jeszcze drzewa rozpinającego:

• Wybieramy jedną z krawędzi o minimalnej wadze i usuwamy ją z S.
• Jeśli ta krawędź łączy dwa różne drzewa, dodajemy ją do lasu L, łącząc dwa odpowiadające sobie drzewa w jedno.
• W przeciwnym razie, krawędź ta jest odrzucana.

Po zakończeniu działania algorytmu, L staje się minimalnym drzewem rozpinającym.

Implementacja i złożoność

Możemy zrealizować zbiór E jako tablicę wszystkich krawędzi uporządkowaną według ich wag. W każdym kroku najmniejsza krawędź to po prostu ta, która znajduje się następna w kolejności. Sortowanie wykonuje się w czasie O(E log E) = O(E log V), ponieważ zakładamy, że E jest mniejsze niż V². W związku z tym log E jest mniejsze niż 2 log V.

Druga faza algorytmu może być zrealizowana przy użyciu struktury zbiorów rozłącznych – początkowo każdy wierzchołek tworzy osobny zbiór, a struktura ta umożliwia sprawdzenie, czy dwa wierzchołki należą do jednego zbioru oraz połączenie dwóch zbiorów w jeden. W implementacji opartej na lesie drzew rozłącznych z kompresją ścieżki, operacje te działają łącznie w czasie O(E α(E, V)), gdzie α to funkcja rosnąca bardzo wolno (odwrotność funkcji Ackermanna).

Łączny czas działania algorytmu wynosi zatem O(E log V), co wynika z pierwszej fazy – sortowania. Jeśli krawędzie są już posortowane lub możliwe jest użycie szybszych algorytmów sortowania (na przykład sortowania przez zliczanie), algorytm działa w czasie O(E α(E, V)).

Przykład

…

Dowód poprawności

Dowód składa się z dwóch części. Najpierw wykazujemy, że graf generowany przez algorytm jest drzewem rozpinającym, a następnie, że jest to drzewo o minimalnej wadze.

Drzewo rozpinające

Niech G będzie spójnym, ważonym grafem, a T podgrafem stworzonym przez algorytm. T nie może zawierać cyklu, ponieważ dodana krawędź, która mogłaby go stworzyć, musiałaby być dodana do drzewa podgrafu, a nie połączyć dwa drzewa, co jest sprzeczne z zasadami algorytmu. T nie może być również niespójne, ponieważ pierwsza napotkana krawędź (ta o najmniejszej wadze) łącząca te składowe zostałaby wybrana przez algorytm (jej istnienie wynika z założenia, że graf wyjściowy jest spójny). Stąd T jest drzewem rozpinającym dla G.

Minimalna waga

Dowód jest przeprowadzony indukcyjnie.

Zobacz też

algorytm Prima

Przypisy

…

Bibliografia

Thomas H. Cormen, Charles Eric Leiserson, Ronald Linn Rivest, Clifford Stein: Wprowadzenie do algorytmów. Krzysztof Diks (tłum.). Wyd. 8. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, seria: Klasyka Informatyki. ISBN 978-832043328-9. OCLC 749241843. (pol.).

Linki zewnętrzne

Rafał Nowak: Implementacja Algorytmu Kruskala w języku C++. rafalnowak.pl, 2008-02-27. [dostęp 2015-06-24]. [zarchiwizowane z tego adresu (2015-06-24)]. (pol.).