Algorytm Prima
Z Wikipedii, wolnej encyclopedia
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].
|
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 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].