PL 
EnglishDomyślny
Українська🌲 Minimalne drzewo rozpinające
Animacja krok po kroku algorytmów MST Kruskala i Prima na losowym grafie ważonym. Koszty krawędzi widoczne na łukach; przełączaj algorytmy i zobacz, jak każdy buduje optymalne drzewo rozpinające.
O tej symulacji
Ta symulacja animuje dwa klasyczne algorytmy zachłanne — Kruskala i Prima — które obliczają minimalne drzewo rozpinające (MST) grafu ważonego: podzbiór krawędzi łączący wszystkie wierzchołki przy możliwie najniższej sumarycznej wadze krawędzi. Wierzchołki są rozrzucone po płótnie i połączone z najbliższymi sąsiadami, a każda krawędź niesie numeryczny koszt. Obserwowanie, jak drzewo rośnie krawędź po krawędzi, pokazuje, jak zupełnie różne strategie dochodzą do tej samej optymalnej struktury — wynik gwarantowany przez własność cięcia drzew rozpinających.
🔬 Co przedstawia
Losowy graf ważony o 8–40 wierzchołkach, każdy połączony w przybliżeniu z czterema najbliższymi sąsiadami, z wagami wyznaczonymi na podstawie odległości na ekranie. Algorytm Kruskala sortuje wszystkie krawędzie według wagi i dodaje najtańszą, która nie tworzy cyklu, wykorzystując strukturę Union-Find (zbiory rozłączne) do wykrywania cykli. Algorytm Prima zamiast tego rozbudowuje pojedyncze drzewo od wierzchołka 0, wielokrotnie dodając najtańszą krawędź prowadzącą do nieodwiedzonego wierzchołka. Oba kończą pracę z dokładnie N−1 krawędziami i tą samą minimalną wagą całkowitą.
🎮 Jak korzystać
Przełączaj między trybem Kruskal i Prim, a następnie ustaw liczbę wierzchołków suwakiem Wierzchołki (8–40). Wybierz prędkość odtwarzania Wolno, Normalnie lub Szybko. Naciśnij Play, aby animować w sposób ciągły, lub Krok, aby przechodzić po jednej decyzji, obserwując krawędzie kandydujące (żółte), zaakceptowane (zielone) i odrzucone (czerwone). Nowy graf generuje nowy układ. Panel boczny śledzi liczbę wierzchołków, łączną liczbę krawędzi, krawędzie MST oraz bieżącą wagę MST.
💡 Czy wiesz, że?
Oba algorytmy są dowodliwie optymalne, choć algorytm Kruskala opublikowano w 1956 roku, a Prima w 1957 (po raz pierwszy opisał go Jarník już w 1930). W grafie o unikalnych wagach krawędzi minimalne drzewo rozpinające jest jednoznaczne, więc Kruskal i Prim zawsze zbiegają do identycznego zestawu krawędzi, mimo że przeszukują graf w zupełnie innej kolejności.
Najczęściej zadawane pytania
Czym jest minimalne drzewo rozpinające?
Drzewo rozpinające to zbiór krawędzi łączący wszystkie wierzchołki grafu bez tworzenia żadnego cyklu, który dla N wierzchołków zawsze wykorzystuje dokładnie N−1 krawędzi. Minimalne drzewo rozpinające to drzewo rozpinające, którego suma wag krawędzi jest najmniejsza z możliwych. Jest szeroko stosowane do projektowania tanich sieci, takich jak okablowanie, rurociągi i połączenia drogowe.
Czym różnią się algorytmy Kruskala i Prima?
Algorytm Kruskala jest zorientowany na krawędzie: sortuje każdą krawędź według wagi i zachłannie dodaje kolejną najtańszą krawędź, o ile nie tworzy ona cyklu, wykorzystując strukturę Union-Find do sprawdzania spójności. Algorytm Prima jest zorientowany na wierzchołki: zaczyna od jednego wierzchołka i zawsze rozszerza istniejące drzewo o najtańszą krawędź do nieodwiedzonego wierzchołka. Przeszukują graf w innej kolejności, ale dają ten sam optymalny wynik.
Co oznaczają kolory i etykiety?
Każda krawędź jest oznaczona swoją wagą całkowitą, obliczoną na podstawie odległości między jej dwoma wierzchołkami. Blade krawędzie nie zostały jeszcze przetworzone, żółte to bieżący kandydat, zielone zostały przyjęte do drzewa, a czerwone zostały odrzucone za tworzenie cyklu. W trybie Prim wypełnione zielone wierzchołki to te, które są już częścią rosnącego drzewa.
Dlaczego niektóre krawędzie są odrzucane w trybie Kruskala?
Kruskal rozpatruje krawędzie od najtańszej do najdroższej, ale dodanie krawędzi między dwoma już połączonymi wierzchołkami utworzyłoby cykl zamiast rozszerzyć drzewo. Struktura Union-Find wykrywa to w czasie niemal stałym, więc taka krawędź jest oznaczana jako odrzucona (czerwona) i pomijana, dzięki czemu wynik pozostaje poprawnym drzewem.
Czy oba algorytmy gwarantują ten sam wynik?
Oba zawsze dają minimalne drzewo rozpinające, więc suma wag jest identyczna. Gdy wszystkie wagi krawędzi są różne, samo MST jest jednoznaczne, co oznacza, że Kruskal i Prim wybierają dokładnie te same krawędzie. Jeśli niektóre wagi się powtarzają, wybrane krawędzie mogą się nieznacznie różnić, ale ogólna minimalna waga pozostaje taka sama.