Primov algoritmus: Rozdiel medzi revíziami
→Časová zložitost: aktualizácia, wikilinky |
→Časová zložitost: preklepy |
||
Riadok 49: | Riadok 49: | ||
| [[binárna halda]] a ''zoznam susedov'' || O((n + m) log(n)) = n log(n) |
| [[binárna halda]] a ''zoznam susedov'' || O((n + m) log(n)) = n log(n) |
||
|- |
|- |
||
| [[Leonardo Pisano Fibonacci|Fibonacciho]] [[halda]] a ''zoznam susedov'' || O(m + n log(n)) |
| [[Leonardo Pisano Fibonacci|Fibonacciho]] [[Halda (dátová štruktúra)|halda]] a ''zoznam susedov'' || O(m + n log(n)) |
||
|} |
|} |
||
Verzia z 15:49, 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
Príklad
Č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á 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 .