Algorytm Prima – Wikipedia, wolna encyklopedia
![]() | Ten artykuł od 2014-06 zawiera treści, przy których brakuje odnośników do źródeł. |
Rodzaj | Wyznaczanie minimalnego drzewa rozpinającego |
---|---|
Struktura danych | |
Złożoność | |
Czasowa | • |
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
[edytuj | edytuj kod]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ści
[edytuj | edytuj kod]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 | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ Cormen i in. 2007 ↓, s. 570.
- ↑ Cormen i in. 2007 ↓, s. 571.
- ↑ 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.).
- ↑ Sysło, Deo i Kowalik 1995 ↓, s. 212.
- ↑ Łukasz Jeleń , Projektowanie algorytmów i metody sztucznej inteligencji. Tablice haszujące, grafy. [online], IIAR PWR, s. 13 [dostęp 2016-03-19] [zarchiwizowane z adresu 2016-03-27] .
- ↑ a b Cormen i in. 2007 ↓, s. 573.
- ↑ Cormen i in. 2007 ↓, s. 574.
Bibliografia
[edytuj | edytuj kod]- Thomas H. Cormen i inni, Wprowadzenie do algorytmów, WNT, 2007 .
- Piotr Stańczyk , Algorytmika Praktyczna w Konkursach Informatycznych [online], styczeń 2007 .
- Maciej Marek Sysło, Narsingh Deo , Janusz S. Kowalik , Algorytmy optymalizacji dyskretnej, wyd. drugie, Warszawa: Wydawnictwo Naukowe PWN, 1995, ISBN 83-01-11818-0 .
- Opis i implementacja algorytmu Prima [online] [dostęp 2014-07-05] .
Linki zewnętrzne
[edytuj | edytuj kod]- Prim’s algorithm code (Internet Archive). algorithm-code.com. [zarchiwizowane z tego adresu (2009-04-25)].
- Implementacja C++ łącznie z komentarzem