Algorytm Prima

Ten artykuł od 2014-06 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do wiarygodnych źródeł. (Dodanie listy źródeł bibliograficznych lub linków zewnętrznych nie jest wystarczające). Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Algorytm Prima – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR)^[1]. 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^[2].

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

Algorytm

Schemat działania^[6]:

• 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) ${\displaystyle O(|E|\cdot \log |V|)}$^[6].
• Przy zastosowaniu kopca Fibonacciego ${\displaystyle O(|E|+|V|\cdot \log |V|),}$ co przy dużej gęstości grafu (takiej, że ${\displaystyle |E|}$ jest ${\displaystyle \omega (|V|\cdot \log |V|)}$) oznacza duże przyspieszenie^[7].

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 ${\displaystyle n}$ algorytmu Prima istnieje minimalne drzewo rozpinające ${\displaystyle Y_{n}}$ zawierające drzewo ${\displaystyle G_{n}}$ powstałe w kroku algorytmu.

W kroku pierwszym do drzewa ${\displaystyle G_{1}}$ dodawany jest dowolny wierzchołek ${\displaystyle v.}$ Ponieważ każde drzewo rozpinające zawiera wszystkie wierzchołki, jako ${\displaystyle Y_{1}}$ możemy wybrać dowolne minimalne drzewo rozpinające.

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

Łatwo zaważyć, że graf ${\displaystyle G_{n}}$ dla ${\displaystyle 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 .
• PiotrP. Stańczyk PiotrP., Algorytmika Praktyczna w Konkursach Informatycznych, styczeń 2007 .
• Maciej MarekM.M. Sysło Maciej MarekM.M., NarsinghN. Deo NarsinghN., Janusz S.J.S. Kowalik Janusz S.J.S., Algorytmy optymalizacji dyskretnej, wyd. drugie, Warszawa: Wydawnictwo Naukowe PWN, 1995, ISBN 83-01-11818-0 .
• Opis i implementacja algorytmu Prima [dostęp 2014-07-05] .

Linki zewnętrzne

• Prim’s algorithm code (Internet Archive). algorithm-code.com. [zarchiwizowane z tego adresu (2009-04-25)].
• Implementacja C++ łącznie z komentarzem