Algorytm Prima

Algorytm Prima

Algorytm Prima to algorytm zachłanny, który służy do wyznaczania tzw. minimalnego drzewa rozpinającego (MDR). Działa na grafach nieskierowanych i spójnych, co oznacza, że krawędzie grafu nie mają przypisanego kierunku, a pomiędzy każdymi dwoma wierzchołkami istnieje ścieżka. Algorytm ma na celu obliczenie podzbioru E’ zbioru krawędzi E, dla którego graf pozostaje spójny, a suma kosztów wszystkich krawędzi w E’ jest minimalna.

Algorytm ten został opracowany w 1930 roku przez czeskiego matematyka Vojtěcha Jarníka, a następnie niezależnie odkryty przez informatyka Roberta C. Prima w 1957 roku oraz Edsgera Dijkstrę w 1959 roku. Z tego powodu algorytm bywa nazywany także algorytmem Dijkstry-Prima, algorytmem DJP, algorytmem Jarníka lub algorytmem Prima-Jarníka.

Algorytm

Schemat działania algorytmu wygląda następująco:

• Utwórz drzewo zawierające jeden wierzchołek, dowolnie wybrany z grafu.
• Utwórz kolejkę priorytetową, zawierającą wierzchołki osiągalne z MDR (na początku będzie to jeden wierzchołek, więc w kolejce znajdą się sąsiedzi początkowego wierzchołka), uporządkowaną według najmniejszego kosztu dotarcia do danego wierzchołka z MDR.
• Powtarzaj, aż drzewo obejmie wszystkie wierzchołki grafu:
  • Wśród nieprzetworzonych wierzchołków (spoza obecnego MDR) wybierz ten, dla którego koszt dojścia z obecnego MDR jest najmniejszy.
  • Dodaj do MDR wierzchołek oraz krawędź realizującą najmniejszy koszt.
  • Zaktualizuj kolejkę priorytetową, uwzględniając nowe krawędzie wychodzące z dodanego wierzchołka.

Złożoność obliczeniowa algorytmu zależy od zastosowanej implementacji kolejki priorytetowej:

• Dla wersji opartej na zwykłym kopcu (lub drzewie czerwono-czarnym): O(|E| ⋅ log |V|).
• Przy użyciu kopca Fibonacciego: O(|E| + |V| ⋅ log |V|), co przy dużej gęstości grafu oznacza znaczące przyspieszenie.

Dowód poprawności

Rozważmy dowolny spójny graf nieskierowany z wagami. Wiadomo, że istnieje przynajmniej jedno minimalne drzewo rozpinające. Udowodnimy, że dla każdego kroku n algorytmu Prima istnieje minimalne drzewo rozpinające Y_n, które zawiera drzewo G_n powstałe w danym kroku algorytmu.

W pierwszym kroku do drzewa G₁ dodawany jest dowolny wierzchołek v. Każde drzewo rozpinające musi zawierać wszystkie wierzchołki, dlatego jako Y₁ możemy wybrać dowolne minimalne drzewo rozpinające.

Dla dowolnego kroku n, gdzie n > 1, graf G_n-1 znajduje się w pewnym minimalnym drzewie rozpinającym Y_n-1. W kroku tym wybierana jest krawędź e, łącząca wierzchołek v_e z wierzchołkiem v_e’, który nie należy do grafu G_n-1.

Jeżeli krawędź e należy do Y_n-1, to możemy przyjąć Y_n = Y_n-1. W przeciwnym razie w drzewie Y_n-1 musi istnieć inna ścieżka łącząca wierzchołki v_e i v_e’, która zawiera pewną krawędź f.

Ta krawędź f łączy wierzchołek v_f z wierzchołkiem v_f’ do grafu G_n-1. Rozważając graf Y_n powstały przez usunięcie krawędzi f z Y_n-1 i dodanie krawędzi e, stwierdzamy, że krawędź e ma wagę mniejszą lub równą wadze krawędzi f.

Jeżeli tak nie jest, krawędź e nie mogłaby być wybrana przez algorytm. Wynika stąd, że suma wag krawędzi w grafie Y_n jest nie większa od sumy wag krawędzi w grafie Y_n-1.

Udowodnijmy jeszcze, że graf Y_n jest drzewem rozpinającym. Dla dowolnych dwóch wierzchołków istnieje w drzewie Y_n-1 ścieżka je łącząca. Jeżeli ta ścieżka nie zawierała krawędzi f, to zawiera się również w grafie Y_n. W przeciwnym przypadku, można ją zastąpić ścieżką, która łączy wierzchołki v_f i v_e, korzystając z krawędzi e oraz ścieżki łączącej wierzchołki v_e i v_f’.

Ostatecznie, graf G_n, dla n = |V|, jest minimalnym drzewem rozpinającym.

Zobacz też

• implementacje algorytmu Prima
• algorytm Borůvki
• algorytm Dijkstry
• algorytm Kruskala

Przypisy

Bibliografia

Thomas H.T.H. Cormen, Thomas H.T.H. i inni, Wprowadzenie do algorytmów, WNT, 2007.

Piotr P. Stańczyk, Algorytmika Praktyczna w Konkursach Informatycznych [online], styczeń 2007.

Maciej M. Sysło, Narsingh N. Deo, Janusz S. Kowalik, Algorytmy optymalizacji dyskretnej, wyd. drugie, Warszawa: Wydawnictwo Naukowe PWN, 1995, ISBN 83-01-11818-0.

Opis i implementacja algorytmu Prima [online] [dostęp 2014-07-05].

Linki zewnętrzne

Prim’s algorithm code (Internet Archive). [zarchiwizowane z tego adresu (2009-04-25)].

Implementacja C++ łącznie z komentarzem