Algorytm Kruskala

Posortuj krawędzie, bierz najkrótszą, nigdy nie zamykaj pętli. Algorytm Kruskala to chyba najprostszy algorytm zachłanny, jaki istnieje, a mimo to zawsze znajduje najtańszy sposób połączenia wszystkich wierzchołków grafu.

Graf, w którym rośnie naraz kilka części drzewa, pominięta krawędź, która zamknęłaby cykl, narysowana czerwoną przerywaną linią, i lista krawędzi do sprawdzenia poniżej
Graf, w którym rośnie naraz kilka części drzewa, pominięta krawędź, która zamknęłaby cykl, narysowana czerwoną przerywaną linią, i lista krawędzi do sprawdzenia poniżej

Idea

Minimalne drzewo rozpinające łączy wszystkie wierzchołki grafu ważonego przy najmniejszej możliwej łącznej długości krawędzi. Algorytm Kruskala nie rozbudowuje jednego drzewa od startu. Patrzy na cały graf naraz, zaczyna od tego, że każdy wierzchołek jest osobną częścią, i łączy części najkrótszą dostępną krawędzią, aż zostanie tylko jedna.

Krok po kroku

Posortuj krawędzie od najkrótszej do najdłuższej. Sprawdzaj je w tej kolejności. Jeśli dwa końce krawędzi leżą w różnych częściach, dodaj ją do drzewa: te dwie części stają się jedną. Jeśli oba końce są już w tej samej części, krawędź zamknęłaby cykl, więc ją pomiń. Przy n wierzchołkach drzewo jest gotowe po n − 1 krawędziach, a pozostałych krawędzi nie trzeba w ogóle oglądać.

Przykład

Weź krawędzie A–B o długości 1, B–C 2, A–C 3, C–D 4 i B–D 5. Kruskal dodaje A–B, potem B–C, która dołącza C do części A–B. Następna jest A–C, ale A i C są już w jednej części, więc zamknęłaby cykl A–B–C i zostaje pominięta. C–D dołącza D i teraz wszystkie cztery wierzchołki tworzą jedno drzewo z trzema krawędziami o łącznej długości 7. B–D, najdłuższa krawędź, nie zostaje nawet sprawdzona.

Union-find

Jedyne trudne pytanie, jakie zadaje algorytm Kruskala, brzmi: czy te dwa wierzchołki są już w tej samej części? Odpowiada na nie struktura union-find. Każda część to małe drzewo dowiązań wskazujących na reprezentanta. Find idzie po dowiązaniach do reprezentanta; union podpina jednego reprezentanta pod drugiego. Kompresja ścieżek, która każdy odwiedzony wierzchołek kieruje wprost na reprezentanta, i łączenie według rozmiaru utrzymują dowiązania tak krótkie, że każde pytanie zajmuje prawie stały czas.

Historia i szybkość

Joseph Kruskal opublikował ten algorytm w 1956 roku, w krótkim artykule w Proceedings of the American Mathematical Society. Najwolniejsze jest sortowanie krawędzi, więc praca rośnie jak E log E dla E krawędzi. Jeśli krawędzie są już posortowane albo ich długości to małe liczby całkowite, jest prawie liniowy.

Wypróbuj

Otwórz aplikację i naciśnij Krok. Krawędzie, które zostały do sprawdzenia, są wypisane pod grafem, od najkrótszej. Każda krawędź, która łączy dwie części, robi się zielona; każda, która zamknęłaby cykl, jest rysowana czerwoną przerywaną linią. Zobacz, jak kilka małych części rośnie w różnych miejscach grafu i się łączy, i zauważ, że ostatnie krawędzie często nie zostają nawet sprawdzone.

Często zadawane pytania

Dlaczego algorytm Kruskala sortuje krawędzie?

Żeby każda dodawana krawędź była najkrótszą, która wciąż łączy dwie części. Ten zachłanny wybór jest zawsze bezpieczny dzięki własności cięcia, a każda pominięta krawędź jest najdłuższa w cyklu, który by zamknęła, więc nigdy nie jest potrzebna.

Czym jest struktura zbiorów rozłącznych?

To inna nazwa union-find: struktura, która przechowuje kolekcję osobnych zbiorów, tu części rosnącego lasu, i potrafi szybko powiedzieć, do którego zbioru należy element, oraz połączyć dwa zbiory.

Czy algorytm Kruskala działa na grafie niespójnym?

Tak. Kończy po prostu z jednym drzewem dla każdej spójnej części grafu, czyli z minimalnym lasem rozpinającym, bo żadna krawędź nie może połączyć części, które nie są połączone.

Czy algorytm Kruskala ma inne zastosowania?

Zatrzymany wcześnie, zanim połączą się ostatnie części, dzieli wierzchołki na klastry: to klasteryzacja metodą pojedynczego wiązania. Uruchomiony na siatce z losowymi długościami krawędzi generuje labirynt.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj algorytm Kruskala