- Bieżący
- W drzewie
- Obok drzewa
- Najlepsza dotąd krawędź
Algorytm Prima
Algorytm Prima buduje minimalne drzewo rozpinające, najtańszy zbiór krawędzi łączący wszystkie wierzchołki, rozbudowując jedno drzewo od startu. W każdym kroku dodaje wierzchołek, do którego da się dojść z drzewa najkrótszą krawędzią. Kliknij wierzchołek, aby zacząć od niego, i przejdź krok po kroku, aby zobaczyć czekające wierzchołki, ich najlepsze krawędzie i rosnące drzewo. 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. Kliknij wierzchołek, aby uczynić go startem: od niego rośnie drzewo. Liczba na każdej krawędzi to jej długość. Pod grafem są wierzchołki czekające na dołączenie, każdy z długością swojej najlepszej krawędzi do drzewa, rysowanej 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
- Kliknij wierzchołek, aby uczynić go startem: od niego rośnie drzewo.
- 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.
- Obserwuj czekające wierzchołki pod grafem, każdy z jego najlepszą krawędzią do drzewa. Nowy graf tworzy inny graf do wypróbowania.
Jak działa algorytm Prima
Zacznij od drzewa z jednym wierzchołkiem. Każdy wierzchołek poza drzewem pamięta swoją najkrótszą krawędź do drzewa, jeśli ją ma. Raz po raz bierz wierzchołek z najkrótszą krawędzią, dodaj go razem z tą krawędzią do drzewa i sprawdź jego krawędzie: jeśli któraś jest krótsza od dotychczasowej najlepszej krawędzi sąsiada, staje się jego najlepszą krawędzią. Gdy dołączą wszystkie wierzchołki, drzewo ma o jedną krawędź mniej, niż jest wierzchołków, a jego łączna długość jest najmniejsza z możliwych.
Prim i Dijkstra
Algorytm Prima i algorytm Dijkstry wyglądają prawie tak samo: oba rozbudowują obszar od startu i trzymają czekające wierzchołki w kolejce priorytetowej. Różnica tkwi w liczbie w kolejce. Dijkstra przechowuje całą odległość wierzchołka od startu; Prim tylko długość jego jednej najlepszej krawędzi do drzewa. Dlatego Dijkstra buduje drzewo najkrótszych ścieżek, a Prim drzewo o najmniejszej łącznej długości, i te dwa drzewa często się różnią.
Często zadawane pytania
Czym jest algorytm Prima?
Algorytmem zachłannym, który buduje minimalne drzewo rozpinające grafu ważonego, rozbudowując jedno drzewo od wierzchołka startowego i zawsze dodając najkrótszą krawędź łączącą drzewo z wierzchołkiem spoza niego.
Czy wierzchołek startowy ma znaczenie?
Tylko dla kolejności: z każdego startu algorytm Prima kończy z drzewem rozpinającym o tej samej najmniejszej łącznej długości. Gdy niektóre krawędzie mają równe długości, samo drzewo może być inne.
Kto wymyślił algorytm Prima?
Pierwszy opisał go Vojtěch Jarník w 1930 roku. Robert Prim odkrył go ponownie w 1957, a Edsger Dijkstra w 1959 roku, dlatego nazywa się go też algorytmem Jarníka lub algorytmem Prima–Jarníka.
Jak szybki jest algorytm Prima?
Z kopcem binarnym praca rośnie jak E log V dla V wierzchołków i E krawędzi. Ze zwykłą tablicą zamiast kopca potrzeba około V² kroków, co jest lepsze dla grafów gęstych, w których prawie każda para wierzchołków jest połączona.
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