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

  • Bieżący
  • W drzewie
  • Obok drzewa
  • Najlepsza dotąd krawędź

Więcej o algorytmie Prima

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

  1. Kliknij wierzchołek, aby uczynić go startem: od niego rośnie drzewo.
  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 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