Algorytm Prima

Algorytm Prima – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR). Mając do dyspozycji graf nieskierowany i spójny, tzn. taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E′ zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E′ jest najmniejsza możliwa.

Algorytm został wynaleziony w 1930 przez czeskiego matematyka Vojtěcha Jarníka, a następnie odkryty na nowo przez informatyka Roberta C. Prima w 1957 oraz niezależnie przez Edsgera Dijkstrę w 1959. Z tego powodu algorytm nazywany jest również czasami algorytmem Dijkstry-Prima, algorytmem DJP, algorytmem Jarníka, albo algorytmem Prima-Jarníka.

Algorytm 
Schemat działania:
 Utwórz drzewo zawierające jeden wierzchołek, dowolnie wybrany z grafu.
 Utwórz kolejkę priorytetową, zawierającą wierzchołki osiągalne z MDR (w tym momencie zawiera jeden wierzchołek, więc na początku w kolejce będą sąsiedzi początkowego wierzchołka), o priorytecie najmniejszego kosztu dotarcia do danego wierzchołka z MDR.
 Powtarzaj, dopóki drzewo nie obejmuje wszystkich wierzchołków 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 obecnego MDR wierzchołek i 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 w zależności od implementacji kolejki priorytetowej:
 Dla wersji opartej na zwykłym kopcu (bądź drzewie czerwono-czarnym) .
 Przy zastosowaniu kopca Fibonacciego  co przy dużej gęstości grafu (takiej, że  jest ) oznacza duże przyspieszenie.

Dowód poprawności 
Weźmy dowolny spójny graf nieskierowany z wagami. Wiemy, że istnieje co najmniej jedno minimalne drzewo rozpinające. Udowodnimy, że dla każdego kroku  algorytmu Prima istnieje minimalne drzewo rozpinające  zawierające drzewo  powstałe w kroku algorytmu.

W kroku pierwszym do drzewa  dodawany jest dowolny wierzchołek  Ponieważ każde drzewo rozpinające zawiera wszystkie wierzchołki, jako  możemy wybrać dowolne minimalne drzewo rozpinające.

Dla dowolnego kroku  gdzie  wiemy, że graf  zawiera się w pewnym minimalnym drzewie rozpinającym  W kroku wybierana jest krawędź  łącząca wierzchołek  należący do grafu  z wierzchołkiem  nienależącym do grafu  Jeżeli krawędź  należy do  to możemy przyjąć  W przeciwnym wypadku, w drzewie  musi istnieć inna ścieżka łącząca wierzchołki  i  Ścieżka taka musi zawierać pewną krawędź  łączącą pewien wierzchołęk  należący do grafu  z pewnym wierzchołkiem  do grafu  nienależącym. Weźmy wtedy graf  powstały przez usunięcie z grafu  krawędzi  i dodanie krawędzi  Krawędź  ma wagę mniejszą lub równą wadze krawędzi  W przeciwnym wypadku krawędź  nie mogłaby być wybrana przez algorytm. Wnioskujemy, że suma wag krawędzi grafu  jest nie większa od sumy wag krawędzi grafu  Udowodnijmy jeszcze, że graf  jest drzewem rozpinającym. Dla dowolnych dwóch wierzchołków istnieje w drzewie  ścieżka je łącząca. Jeżeli ścieżka ta nie zawierała krawędzi  to zawiera się ona też w grafie  Jeżeli ścieżka ta zawiera krawędź  to można ją zastąpić ścieżką łączącą wierzchołki  z  krawędzią  i ścieżką łączącą wierzchołki  z 

Łatwo zaważyć, że graf  dla  jest minimalnym drzewem rozpinającym.

Zobacz też 
 implementacje algorytmu Prima
 algorytm Borůvki
 algorytm Dijkstry
 algorytm Kruskala

Przypisy

Bibliografia

Linki zewnętrzne 
 
 Implementacja C++ łącznie z komentarzem

Algorytmy grafowe