Algorytm Kruskala
Algorytm Kruskala to algorytm grafowy służący do wyznaczania minimalnego drzewa rozpinającego w spójnym, nieskierowanym grafie ważonym. Jego celem jest znalezienie drzewa obejmującego wszystkie wierzchołki grafu o najmniejszej możliwej wadze. Algorytm został opisany przez Josepha Kruskala w 1956 roku.
Opis algorytmu
Algorytm Kruskala przebiega w kilku krokach:
- Utwórz las L z wierzchołków grafu, gdzie każdy wierzchołek stanowi osobne drzewo.
- Utwórz zbiór S zawierający wszystkie krawędzie grafu.
- Dopóki zbiór S nie jest pusty, a L nie stanowi jeszcze drzewa rozpinającego:
- Wybierz krawędź o minimalnej wadze z S i usuń ją.
- Jeśli krawędź łączy dwa różne drzewa, dodaj ją do lasu L, łącząc te drzewa.
- W przeciwnym razie, odrzuć tę krawędź.
Po zakończeniu algorytmu, L będzie minimalnym drzewem rozpinającym.
Implementacja i złożoność
W celu implementacji algorytmu można użyć tablicy krawędzi posortowanych według wag. W każdym kroku wystarczy wybrać następną krawędź. Sortowanie krawędzi odbywa się w czasie , co można także zapisać jako . Następnie wykorzystuje się struktury zbiorów rozłącznych, co pozwala na efektywne łączenie i sprawdzanie zbiorów. Całkowity czas działania algorytmu wynosi . W przypadku, gdy krawędzie są już posortowane, czas działania może wynosić .
Dowód poprawności
Dowód poprawności algorytmu Kruskala składa się z dwóch części:
- Udowodnienie, że wynikowy graf jest drzewem rozpinającym.
- Udowodnienie, że jest to drzewo o minimalnej wadze.
Drzewo rozpinające
Niech będzie spójnym, ważonym grafem, a podgrafem wygenerowanym przez algorytm. nie może zawierać cyklu, ponieważ każda dodana krawędź łączy dwa różne drzewa. Ponadto, nie może być niespójny, ponieważ pierwsza napotkana krawędź łącząca różne składowe musi być wybrana przez algorytm. W ten sposób stanowi drzewo rozpinające
Minimalna waga
Dowód minimalnej wagi uzyskuje się w drodze indukcji.
