Otwórz menu główne

Algorytm Primaalgorytm 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 Prima
Rodzaj Wyznaczanie minimalnego drzewa rozpinającego
Struktura danych graf
Złożoność
Czasowa
– przy zastosowaniu kopca Fibonacciego
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


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


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 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].

Spis treści

AlgorytmEdytuj

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)  [6].
  • Przy zastosowaniu kopca Fibonacciego   co przy dużej gęstości grafu (takiej, że   jest  ) oznacza duże przyspieszenie[7].

Dowód poprawnościEdytuj

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żEdytuj

PrzypisyEdytuj

  1. Cormen i in. 2007 ↓, s. 570.
  2. Cormen i in. 2007 ↓, s. 571.
  3. Vojtěch Jarník, O jistém problému minimálním, „Práce Moravské Přírodovědecké Společnosti”, 6, 1930, s. 57–63 (cz.).
  4. Sysło, Deo i Kowalik 1995 ↓, s. 212.
  5. Łukasz Jeleń, Projektowanie algorytmów i metody sztucznej inteligencji. Tablice haszujące, grafy., IIAR PWR, s. 13 [dostęp 2016-03-19] [zarchiwizowane z adresu 2016-03-27].
  6. a b Cormen i in. 2007 ↓, s. 573.
  7. Cormen i in. 2007 ↓, s. 574.

BibliografiaEdytuj

Linki zewnętrzneEdytuj