Algorytm Kruskala

Minimalne drzewo rozpinające, tworzenie (1) Przykładowe wykonania algorytmu Kruskala
Matroid MST (2) Reprezentacja problemu minimalnego drzewa rozpinającego za pomocą matroidu (kliknij ilustrację, aby powiększyć)

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.

Działanie algorytmu

Algorytm polega na dołączaniu do rozwiązania kolejno najkrótszych możliwych krawędzi, aż do otrzymania drzewa rozpinającego. Algorytm ten można bardziej formalnie zapisać następująco:

  1. Posortuj krawędzie rosnąco według ich wag, umieść je w kolejce.
  2. Pobierz z kolejki krawędź o najmniejszej wadze, usuń ją z kolejki.
  3. Jeśli wierzchołki łączone przez tę krawędź należą do różnych drzew (wówczas dołączenie krawędzi nie spowoduje utworzenia cyklu), dołącz krawędź do rozwiązania.
  4. Jeśli liczba krawędzi dołączonych do rozwiązania wynosi v-1 (v jest liczbą wierzchołków), zakończ działanie algorytmu. W przeciwnym razie przejdź do punktu 2.

Główna pętla algorytmu wykona się maksymalnie e razy (e jest liczbą krawędzi). W trakcie każdego przebiegu pętli trzeba jednak sprawdzić, czy daną krawędź można dołączyć do rozwiązania. Złożoność obliczeniowa algorytmu zależy od sposobu implementacji sprawdzania tego warunku, a także od sposobu sortowania kolejki krawędzi.

Aby sprawdzać, czy wierzchołki należą do różnych drzew, możemy wykorzystać zbiory wierzchołków. Na początku każdy wierzchołek będzie w osobnym zbiorze. Za każdym razem przed dołączeniem krawędzi sprawdzamy, czy wierzchołki znajdują się w różnych zbiorach. Jeśli tak, krawędź dołączamy do rozwiązania, a te dwa zbiory scalamy.

Zwracanie rozwiązań optymalnych

Algorytm Kruskala (pomimo, że jako algorytm zachłanny zalicza się do heurystyk) zawsze zwraca rozwiązanie optymalne. Problem wyznaczania minimalnego drzewa rozpinającego można przedstawić za pomocą matroidu – przykład jest pokazany na rysunku (2). Udowodniono, że w takim przypadku podejście zachłanne daje gwarancję znalezienia rozwiązania optymalnego. Pełen dowód jest dostępny w książce [1].

Bibliografia

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 5 kwietnia 2017 12:16, ostatnia edycja: 24 kwietnia 2020 19:28.

REKLAMA

Zobacz też

Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.

→ Czytaj całość

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość

Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).

→ Czytaj całość
Polityka prywatnościKontakt