Primov algoritmus: Rozdiel medzi revíziami
aktualizácia |
→Časová zložitost: preklepy |
||
Riadok 52: | Riadok 52: | ||
|} |
|} |
||
Jednoduchá implementace s použitím reprezentace grafu pomocí [[matice sousednosti]] a prohledáváním pole cen má [[Asymptotická složitost|časovou složitost]] ''O(n<sup>2</sup>)''. S použitím [[binární halda|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 halda|Fibonacciho haldy]] složitost snížíme až na ''O(m + n log n)'', což je obzvláště rychlé u grafů, kde ''m'' je <math>\Omega(n log n)</math>. |
Jednoduchá implementace s použitím reprezentace grafu pomocí [[matice sousednosti]] a prohledáváním pole cen má [[Asymptotická složitost|časovou složitost]] ''O(n<sup>2</sup>)''. S použitím [[binární halda|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 halda|Fibonacciho haldy]] složitost snížíme až na ''O(m + n log n)'', což je obzvláště rychlé u grafů, kde ''m'' je <math>\Omega(n log n)</math>. |
||
Verzia z 15:29, 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 .