Algorytm Prima
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
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.
Spis treści |
[edytuj] 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 go do obecnego MDR
- 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) O(E log(V))
- Przy zastosowaniu kopca Fibonacciego O(E + V log(V)), co przy dużej gęstości grafu (takiej, że E jest ω(V log (V)) oznacza duże przyspieszenie.
[edytuj] Dowód poprawności
Poprawność algorytmu polega na tym, iż w każdym kroku algorytm konstruuje MDR (za każdym razem wybierane są krawędzie o najmniejszej wadze) dla coraz większego zbioru wierzchołków. To indukuje stwierdzenie, iż w końcu uzyskiwane jest drzewo rozpinające dla całego grafu G.
[edytuj] Zobacz też
[edytuj] Bibliografia
- Piotr Stańczyk: Algorytmika Praktyczna w Konkursach Informatycznych.
- http://www.algorytm.org/algorytmy-grafowe/algorytm-prima.html
