Primov algoritmus: Rozdiel medzi revíziami

Odobraných 8 bajtov ,  pred 11 rokmi
chýba zhrnutie úprav
d (štylistika)
Bez shrnutí editace
'''Primov algoritmus ''' (známy aj ako '''Jarníkov algoritmus''', '''Primov-Jarníkov algoritmus''' alebo aj '''DJP algoritmus''') je v informatike [[pažravý algoritmus|greedy algoritmus]] hľadajúci minimálnu [[kostra grafu | kostru]] súvislého ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí [[strom (graf)|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 na Jarníkovi 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' = {}
* Výstup: T(V',E') je minimálna kostra grafu
 
== Časová zložitostzložitosť ==
 
== Časová zložitost ==
{| class="wikitable"
! Dátová štruktúra s ohodnotením hrán !! Celková č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 <math>\Omega(n)</math>.
 
 
== Príklad ==
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! Obrázok !! Popis
|-
|Teraz 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.
 
 
== Referencie ==
* [[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:Algoritmy]]
 
 
 
 
 
[[cs:Jarníkův algoritmus]]
113 816

úprav