- Bieżący
- W drzewie
- Zamknęłaby cykl
Algorytm Kruskala
Algorytm Kruskala buduje minimalne drzewo rozpinające, najtańszy zbiór krawędzi łączący wszystkie wierzchołki, w najprostszy możliwy sposób: bierz krawędzie od najkrótszej do najdłuższej i zachowuj każdą, chyba że zamknęłaby cykl. Przejdź krok po kroku, aby zobaczyć, jak osobne części rosną i łączą się w jedno drzewo, oraz które krawędzie są pomijane. Naciśnij Odtwórz, aby zobaczyć, jak rośnie drzewo, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Liczba na każdej krawędzi to jej długość. Pod grafem są krawędzie, które zostały do sprawdzenia, od najkrótszej do najdłuższej; krawędź, której końce są już połączone, zamknęłaby cykl i jest rysowana czerwoną przerywaną linią. Nowy graf tworzy inny graf; wybierz, ile ma mieć wierzchołków i krawędzi. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku.
- Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Krawędzie, które zostały do sprawdzenia, są wypisane pod grafem, od najkrótszej.
- Zwróć uwagę na krawędzie rysowane czerwoną przerywaną linią: zamknęłyby cykl. Nowy graf tworzy inny graf do wypróbowania.
Jak działa algorytm Kruskala
Posortuj wszystkie krawędzie od najkrótszej do najdłuższej. Zacznij od tego, że każdy wierzchołek jest osobną częścią. Sprawdzaj krawędzie po kolei: jeśli krawędź łączy dwie różne części, trafia do drzewa, a te dwie części stają się jedną; jeśli oba jej końce są już w tej samej części, zamknęłaby cykl, więc ją pomiń. Zakończ, gdy wszystko jest jedną częścią. Dzieje się to po o jedną krawędź mniej, niż jest wierzchołków, często na długo przed sprawdzeniem ostatniej krawędzi.
Union-find
Przy każdej krawędzi algorytm Kruskala musi zapytać, czy jej dwa końce są już połączone. Struktura union-find odpowiada na to szybko: każda część ma jednego reprezentanta, find idzie po dowiązaniach do niego, a union podpina jednego reprezentanta pod drugiego. Dzięki dwóm prostym sztuczkom, kompresji ścieżek i łączeniu według rozmiaru, każde pytanie zajmuje prawie stały czas, więc najwolniejsze jest sortowanie krawędzi, a praca rośnie jak E log E.
Często zadawane pytania
Czym jest algorytm Kruskala?
Algorytmem zachłannym, który buduje minimalne drzewo rozpinające: sortuje wszystkie krawędzie od najkrótszej do najdłuższej i dodaje każdą, która nie zamyka cyklu z krawędziami już wybranymi.
Jak algorytm Kruskala wykrywa cykl?
Krawędź zamyka cykl dokładnie wtedy, gdy jej dwa końce są już połączone wybranymi krawędziami. Struktura union-find śledzi, które wierzchołki są połączone, i odpowiada na to pytanie prawie natychmiast.
Dlaczego algorytm Kruskala działa?
Dzięki własności cyklu: najdłuższa krawędź w dowolnym cyklu nigdy nie jest potrzebna w minimalnym drzewie rozpinającym. Każda krawędź pominięta przez Kruskala jest najdłuższa w cyklu, który by zamknęła, bo wszystkie krawędzie przed nią były krótsze lub równe.
Kiedy używać Kruskala zamiast Prima?
Algorytm Kruskala jest prosty i szybki na grafach rzadkich i działa wprost na zwykłej liście krawędzi. Algorytm Prima pasuje do grafów gęstych i grafów zapisanych jako listy sąsiedztwa. Oba znajdują drzewo o tej samej łącznej długości.
Czy mój graf jest gdzieś wysyłany?
Nie. Graf powstaje i drzewo jest budowane w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora