Primov algoritmus: Rozdiel medzi revíziami
→Časová zložitost: preklepy |
preklepy |
||
Riadok 1: | Riadok 1: | ||
'''Primov algoritmus ''' (známy aj ako '''Jarníkov algoritmus''', '''Primov-Jarníkov algoritmus''' alebo aj '''DJP algoritmus''') je v teórii grafov algoritmus hľadajúci minimálnu kostru ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí [[strom (graf)]] 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]] tento algoritmus 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 teórii grafov algoritmus hľadajúci minimálnu kostru ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí [[strom|strom (graf)]] 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]] tento algoritmus 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 == |
Verzia z 15:31, 27. máj 2011
Primov algoritmus (známy aj ako Jarníkov algoritmus, Primov-Jarníkov algoritmus alebo aj DJP algoritmus) je v teórii grafov algoritmus hľadajúci minimálnu kostru ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí strom (graf) 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 tento algoritmus 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
Príklad
Časová zložitost
Datová struktura s ohodnocením hran | Celková časová složitost |
---|---|
matica susednosti | n2 |
binární halda (v pseudokódu níže) a seznam sousedů | O((n + m) log(n)) = n log(n) |
Fibonacciho halda a seznam sousedů | m + n log(n) |
Jednoduchá implementace s použitím reprezentace grafu pomocí matice sousednosti a prohledáváním pole cen má časovou složitost O(n2). S použitím binární haldy a seznamu sousedů dosáhneme složitosti O(m log n), kde m je počet hran a n je počet vrcholů. S použitím sofistikované Fibonacciho haldy složitost snížíme až na O(m + n log n), což je obzvláště rychlé u grafů, kde m je Syntaktická analýza (parsing) neúspešná (MathML s fallbackom na SVG alebo PNG (odporúčané pre moderné prehliadače a nástroje pre zjednodušenie prístupu): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „http://localhost:6011/sk.wikipedia.org/v1/“:): {\displaystyle \Omega(n log n)} .