Primov algoritmus: Rozdiel medzi revíziami
d →Referencie: externé odkazy |
štylistika |
||
Riadok 1: | Riadok 1: | ||
'''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. |
'''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 == |
== Popis == |
||
Riadok 10: | Riadok 11: | ||
** Pridaj ''v'' do V', pridaj (u,v) do E' |
** Pridaj ''v'' do V', pridaj (u,v) do E' |
||
* Výstup: T(V',E') je minimálna kostra grafu |
* Výstup: T(V',E') je minimálna kostra grafu |
||
== Časová zložitost == |
== Časová zložitost == |
||
Riadok 24: | Riadok 26: | ||
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>. |
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>. |
||
⚫ | |||
⚫ | |||
{| border=1 cellspacing=2 cellpadding=5 class="wikitable" |
{| border=1 cellspacing=2 cellpadding=5 class="wikitable" |
||
! Obrázok !! Popis |
! Obrázok !! Popis |
||
Riadok 53: | Riadok 55: | ||
|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. |
|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 == |
== 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. |
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 == |
== Referencie == |
Verzia z 18:37, 27. máj 2011
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 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 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' = {}
- Opakuj, kým neplatí, že 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žitost
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
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
- 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.
V tomto článku je použitý preklad časti textu z článku Prim's algorithm na anglickej Wikipedii.