Primov algoritmus: Rozdiel medzi revíziami
preklepy |
→Časová zložitost: aktualizácia, wikilinky |
||
Riadok 43: | Riadok 43: | ||
== Časová zložitost == |
== Časová zložitost == |
||
{| class="wikitable" |
{| class="wikitable" |
||
! |
! Dátová štruktúra s ohodnotením hrán !! Celková časová zložitosť |
||
|- |
|- |
||
| |
| matica susednosti || O(n<sup>2<sup>) |
||
|- |
|- |
||
| [[ |
| [[binárna halda]] a ''zoznam susedov'' || O((n + m) log(n)) = n log(n) |
||
|- |
|- |
||
| [[Fibonacciho halda]] a '' |
| [[Leonardo Pisano Fibonacci|Fibonacciho]] [[halda]] a ''zoznam susedov'' || O(m + n log(n)) |
||
|} |
|} |
||
Verzia z 15:48, 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 .