Primov algoritmus: Rozdiel medzi revíziami

Pridané 4 bajty ,  pred 11 rokmi
štylistika
d (→‎Referencie: externé odkazy)
(štylistika)
'''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]] 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 ==
** Pridaj ''v'' do V', pridaj (u,v) do E'
* Výstup: T(V',E') je minimálna kostra grafu
 
 
== Časová zložitost ==
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 ==
 
== 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 ==
47

úprav