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ť 
 Dátová štruktúra s ohodnotením hrán    Celková časová zložitosť   matica susednosti  O(n2) binárna halda a zoznam susedov  O((n + m) log(n)) = n log(n) Fibonacciho halda a zoznam susedov  O(m + n log(n))

Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť O(n2). 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 .

 Príklad 
 Obrázok  Popis200pxToto je náš pôvodný ohodnotený graf. Čísla na okrajoch hrán označujú ich váhu.200pxZ grafu vyberieme ľubovoľný vrchol. V tomto prípade vrchol D. Tým nám vznikne podgraf. Vrcholy A, B, E a F sú susednými vrcholmi D, teda sú s ním spojené hranou. Vrchol A je od vrcholu D vzdialený najmenej a bude vybraný ako druhý vrchol, spolu s hranou AD.200pxĎalším vybraným vrcholom bude vrchol, ktorý ma najmenšiu vzdialenosť od D alebo A. B má vzdialenosť od A 7 a od D 9. E je od D vzdialený 15 a F zase 6. Cena hrany DF je najnižšia, preto ako ďalší vrchol vyberieme F a ako hranu DF.  200pxAlgoritmus pokračuje ako v predchádzajúcich krokoch. Vyberieme vrchol B, a hranu AB.200pxV tomto prípade si môžeme vybrať medzi troma ešte nevybranými vrcholmi C, E a G. Spomedzi nich má E najmenšiu vzdialenosť od už vybraných vrcholov (7 od B). Preto vyberieme vrchol E a hranu BE.200pxJediné vrcholy prichádzajúce do úvahy sú C a G. C je vzdialený 5 od E a G je vzdialený 9 od E. Vyberieme C spolu s hranou EC.200pxVrchol G je jediný zvyšný vrchol. Od F má vzdialenosť 11, a od E 9. K E je bližšie, preto spolu s ním vyberieme aj hranu EG.200pxTeraz sú už vybrané všetky vrcholy a teda sme získali minimálnu kostru grafu (vyznačená zelenou farbou). Celková váha kostry je 39.

 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