Algorytm Prima
Wyobraź sobie, że kładziesz kabel od elektrowni: najpierw podłączasz najbliższe miasto, potem to, które jest najbliżej czegokolwiek już podłączonego, i tak dalej. To jest algorytm Prima i zawsze kończy się najtańszą możliwą siecią.
Idea
Minimalne drzewo rozpinające łączy wszystkie wierzchołki grafu ważonego przy najmniejszej możliwej łącznej długości krawędzi. Algorytm Prima buduje je, rozbudowując jedno drzewo od startu na zewnątrz. Drzewo nigdy nie rozpada się na części: w każdym kroku dołącza do niego dokładnie jeden nowy wierzchołek, przez najkrótszą krawędź wychodzącą z drzewa.
Krok po kroku
Włóż start do drzewa. Dla każdego wierzchołka poza drzewem zapamiętaj jego najlepszą krawędź: najkrótszą krawędź do dowolnego wierzchołka w drzewie. Potem powtarzaj: wybierz wierzchołek spoza drzewa z najkrótszą najlepszą krawędzią, dodaj go do drzewa razem z tą krawędzią i sprawdź jego krawędzie. Sąsiad spoza drzewa, do którego da się teraz dojść krótszą krawędzią, dostaje ją jako nową najlepszą. Zakończ, gdy wszystkie wierzchołki są w drzewie.
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 i zacznij od A. Krawędzie A dają B najlepszą krawędź 1, a C najlepszą krawędź 3. B jest najbliżej, więc dołącza przez A–B; jego krawędzie poprawiają C do 2 i dają D 5. C dołącza przez B–C, a jego krawędź C–D poprawia D do 4. Na koniec D dołącza przez C–D. Drzewo A–B, B–C, C–D ma łączną długość 1 + 2 + 4 = 7.
Dlaczego to działa
W każdym kroku wierzchołki są podzielone na dwie grupy: te w drzewie i te poza nim. Własność cięcia mówi, że najkrótsza krawędź między dwiema takimi grupami zawsze należy do jakiegoś minimalnego drzewa rozpinającego. Prim zawsze dodaje dokładnie tę krawędź, więc zbudowane dotąd drzewo zawsze da się uzupełnić do minimalnego drzewa rozpinającego, a gdy dołączą wszystkie wierzchołki, samo nim jest.
Historia i szybkość
Czeski matematyk Vojtěch Jarník opublikował ten algorytm w 1930 roku. Robert Prim odkrył go ponownie w Bell Labs w 1957 roku, a Edsger Dijkstra jeszcze raz w 1959 roku. Gdy czekające wierzchołki są w kopcu binarnym, praca rośnie jak E log V dla V wierzchołków i E krawędzi; ze zwykłą tablicą to około V², co jest lepsze, gdy prawie każda para wierzchołków jest połączona. Z kopcem Fibonacciego to E + V log V.
Wypróbuj
Otwórz aplikację, kliknij wierzchołek, aby od niego zacząć, i naciśnij Krok. Wierzchołki w drzewie są zielone, czekające niebieskie, a najlepsza krawędź każdego czekającego wierzchołka jest rysowana przerywaną linią. Czekające wierzchołki są wypisane pod grafem z długością ich najlepszej krawędzi, od najkrótszej: pierwszy dołącza jako następny. Zaczynaj od różnych wierzchołków i zobacz, jak zmienia się kolejność, a łączna długość pozostaje ta sama.
Często zadawane pytania
Czym różni się algorytm Prima od algorytmu Dijkstry?
Oba rozbudowują obszar od startu przy użyciu kolejki priorytetowej. Prim ocenia czekający wierzchołek według długości jego jednej najlepszej krawędzi do drzewa; Dijkstra według całej jego odległości od startu. Prim daje minimalne drzewo rozpinające, Dijkstra drzewo najkrótszych ścieżek.
Czy algorytm Prima działa z ujemnymi długościami krawędzi?
Tak. W przeciwieństwie do algorytmu Dijkstry Prim porównuje tylko krawędzie między sobą, więc ujemne długości nie sprawiają kłopotu: nadal znajduje drzewo rozpinające o najmniejszej sumie.
Co, jeśli graf nie jest spójny?
Wtedy algorytm Prima zatrzymuje się, gdy dotrze do wszystkich wierzchołków, do których może: daje minimalne drzewo rozpinające tylko dla części zawierającej start. Uruchomienie go ponownie od wierzchołka, do którego jeszcze nie dotarł, daje minimalny las rozpinający.
Który jest lepszy: algorytm Prima czy Kruskala?
Żaden nie wygrywa zawsze. Prim pasuje do grafów gęstych i grafów zapisanych jako listy sąsiedztwa; Kruskal do grafów rzadkich podanych jako lista krawędzi. Oba znajdują drzewo o tej samej łącznej długości.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj algorytm Prima