Primov algoritmus

**Primov algoritmus ** (známy aj ako **Jarníkov algoritmus**, **Primov-Jarníkov algoritmus** alebo aj **DJP algoritmus**) je v informatike greedy algoritmus hľadajúci minimálnu kostru súvislého ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí strom obsahujúci všetky vrcholy pôvodného grafu a súčet ohodnotenia hrán z tejto množiny je minimálny. Algoritmus patrí medzi najefektívnejšie a najelegantnejšie implementovateľné algoritmy s týmto účelom. Prvýkrát algoritmus popísal český matematik Vojtěch Jarník roku 1930. V roku 1957 ho nezávisle od Jarníka popísal americký matematik a informatik Robert Clay Prim a potom ešte raz v roku 1959 tento algoritmus znovu objavil holandský informatik Edsger Wybe Dijkstra a na jeho základe vytvoril svoj Dijkstrov algoritmus na hľadanie najkratšej cesty v ohodnotenom grafe.

## Popis
Algoritmus začína s jedným vrcholom a postupne pridáva ďalšie, čím zväčšuje veľkosť stromu dovtedy, kým neobsahuje všetky vrcholy.
* Vstup: súvislý ohodnotený graf G(V,E)
* Inicializácia: V' = {x}, kde x je ľubovoľný vrchol z V, E' = {}
* Opakuj, až kým nebude platiť V'=V:
** Vyber hranu (u,v) z E s minimálnou cenou tak, že *u* patrí V' a *v* nepatrí V'
** Pridaj *v* do V', pridaj (u,v) do E'
* Výstup: T(V',E') je minimálna kostra grafu

## Časová zložitosť

Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť *O(n<sup>2</sup>)*. S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť *O(m log n)*, kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na *O(m + n log n)*, čo je výhodné najmä pri grafoch, kde *m* je \Omega(n).

## Príklad

## Dôkaz korektnosti algoritmu
Nech *G* je súvislý ohodnotený graf. V každej iterácii Primovho algoritmu je pridaná hrana, ktorá má jeden vrchol v podgrafe vytvárajúcom kostru a vrchol mimo tohto podgrafu. Pretože *G* je súvislý, existuje vždy cesta do každého vrcholu. Výstup *Y* Primovho algoritmu je strom, pretože vrchol a hrana, ktoré sú pridané do *Y* sú spojené. Nech *Y1* je minimálna kostra *G*. Ak *Y1=Y*, tak *Y* je minimálna kostra. Inak, nech *e* je prvá hrana pridaná počas konštrukcie *Y*, ktorá nie je v *Y1*, a *V* nech je množina vrcholov spojených hranami pridanými pred pridaním *e*. Potom jeden koncový bod *e* je vo *V* a druhý nie je. Pretože *Y1* je kostra *G*, existuje cesta v *Y1* spájajúca tieto dva koncové vrcholy. Keď prechádzame pozdĺž tejto cesty, musíme naraziť na hranu *f* spájajúcu vrchol vo *V* s vrcholom, ktorý nie je vo *V*. Teraz, v iterácii, keď je pridávaná hrana *e* do *Y*, *f* by mohla byť pridaná tiež a mohla by byť pridaná namiesto *e*, ak by jej ohodnotenie bolo menšie ako *e*. Pretože *f* nebola pridaná, ohodnotenie *f* nie je menšie ako ohodnotenie *e*. Nech *Y2* je graf získaný z *Y1* odstránením *f* a pridaním *e*. Je ľahké ukázať, že *Y2* je súvislý, má ten istý počet hrán ako *Y1* a celková váha jeho hrán nie je väčšia ako v *Y1*, preto je to tiež minimálna kostra *G* a obsahuje *e* a všetky hrany pridané pred *e* počas konštrukcie *V*. Opakovaním vyššie uvedených krokov vieme získať minimálnu kostru grafu *G*, ktorá je identická s *Y*. Toto dokazuje, že *Y* je minimálna kostra. 

## Pozri aj
* Kruskalov algoritmus
## Referencie
* V. Jarník: *O jistém problému minimálním*, Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63.
* R. C. Prim: *Shortest connection networks and some generalisations*. In: *Bell System Technical Journal*, 36 (1957), pp. 1389–1401
* D. Cherition and R. E. Tarjan: *Finding minimum spanning trees*. In: *SIAM Journal of Computing*, 5 (Dec. 1976), pp. 724–741
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.

## Zdroje
*V tomto článku je použitý preklad časti textu z článku Prim's algorithm na anglickej Wikipedii.*

Kategória:Grafové algoritmy
Kategória:Eponymické termíny v informatike