Algorytm Prima

Z testwiki
Przejdź do nawigacji Przejdź do wyszukiwania

Szablon:Dopracować Szablon:Algorytm infobox Algorytm Prima – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR)Szablon:Odn. 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żliwaSzablon:Odn.

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

Algorytm

Schemat działaniaSzablon:Odn:

  • 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:

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 n algorytmu Prima istnieje minimalne drzewo rozpinające Yn zawierające drzewo Gn powstałe w kroku algorytmu.

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

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

Łatwo zaważyć, że graf Gn dla n=|V| jest minimalnym drzewem rozpinającym.

Zobacz też

Przypisy

Szablon:Przypisy

Bibliografia

Linki zewnętrzne

Szablon:Teoria grafów

  1. ↑ Szablon:Cytuj
  2. ↑ Szablon:Cytuj
Źródło: „https://pl.wiki.beta.math.wmflabs.org/w/index.php?title=Algorytm_Prima&oldid=721”