Krawędzie drzewa
Łączna długość
Sprawdzone krawędzie

  • Bieżący
  • W drzewie
  • Obok drzewa
  • Najlepsza dotąd krawędź
  • Zamknęłaby cykl

Więcej o minimalnych drzewach rozpinających

Minimalne drzewo rozpinające

Chcesz połączyć kablem każde miasto, wodociągiem każdy dom albo każdy komputer w sieci, zużywając jak najmniej materiału. Odpowiedzią jest minimalne drzewo rozpinające: zbiór krawędzi, który łączy wszystkie wierzchołki przy najmniejszej łącznej długości. Wybierz algorytm Kruskala lub Prima i przechodź krok po kroku, aby zobaczyć, jak drzewo rośnie, za każdym razem o najkrótszą dozwoloną krawędź. 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. Wybierz algorytm: Kruskal sprawdza krawędzie od najkrótszej do najdłuższej, Prim rozbudowuje jedno drzewo od startu; kliknij wierzchołek, aby uczynić go startem dla Prima. Liczba na każdej krawędzi to jej długość. Pod grafem jest lista krawędzi, które zostały do sprawdzenia, albo wierzchołków czekających na dołączenie, z długością ich najlepszej krawędzi do drzewa. 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

  1. Wybierz algorytm Kruskala lub Prima. W przypadku Prima kliknij wierzchołek, aby uczynić go startem.
  2. 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.
  3. Obserwuj, jak krawędzie dołączają do drzewa, a łączna długość rośnie. Nowy graf tworzy inny graf do wypróbowania.

Algorytm Kruskala

Posortuj wszystkie krawędzie od najkrótszej do najdłuższej i sprawdzaj je w tej kolejności. Jeśli krawędź łączy dwie części, które nie są jeszcze połączone, trafia do drzewa. Jeśli jej dwa końce są już połączone przez drzewo, zamknęłaby cykl, więc zostaje pominięta. Zakończ, gdy drzewo ma o jedną krawędź mniej, niż jest wierzchołków. Aby szybko sprawdzić, czy dwa wierzchołki są już połączone, algorytm Kruskala przechowuje części w strukturze union-find.

Algorytm Prima

Zacznij od drzewa z jednym wierzchołkiem. Każdy wierzchołek poza drzewem pamięta swoją najkrótszą krawędź do drzewa. Raz po raz dodawaj wierzchołek, którego krawędź jest najkrótsza, razem z tą krawędzią, i sprawdzaj jego krawędzie: któraś może dać sąsiadowi krótszą drogę do drzewa. Algorytm Prima przypomina algorytm Dijkstry, ale porównuje pojedyncze krawędzie, a nie całe odległości od startu. Oba algorytmy zawsze kończą z tą samą łączną długością.

Często zadawane pytania

Co to jest minimalne drzewo rozpinające?

W spójnym grafie, którego krawędzie mają długości, drzewo rozpinające to zbiór krawędzi łączący wszystkie wierzchołki bez żadnego cyklu; przy n wierzchołkach ma zawsze n − 1 krawędzi. Minimalne drzewo rozpinające to drzewo rozpinające o jak najmniejszej łącznej długości.

Czym różni się algorytm Kruskala od algorytmu Prima?

Algorytm Kruskala przegląda krawędzie całego grafu od najkrótszej do najdłuższej i łączy osobne części w jedno drzewo. Algorytm Prima rozbudowuje jedno drzewo od startu, zawsze dodając najkrótszą krawędź, która z niego wychodzi. Oba są zachłanne i znajdują drzewo o tej samej łącznej długości; Kruskal pasuje do grafów rzadkich, Prim do gęstych.

Czy minimalne drzewo rozpinające jest jedyne?

Tak, gdy wszystkie długości krawędzi są różne. Gdy niektóre są równe, może być kilka drzew o tej samej najmniejszej sumie, a algorytmy mogą wybrać różne, zależnie od tego, jak wybierają spośród równych krawędzi.

Czy minimalne drzewo rozpinające to to samo co najkrótsze ścieżki?

Nie. Minimalne drzewo rozpinające ma małą łączną długość wszystkich krawędzi, ale ścieżka między dwoma wierzchołkami w drzewie może być dużo dłuższa niż ich najkrótsza ścieżka. Do najkrótszych ścieżek użyj algorytmu Dijkstry.

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