A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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 súvislého 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 od Jarníka 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, až kým nebude platiť 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žitosť
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.
Pozri aj
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.
Zdroje
V tomto článku je použitý preklad časti textu z článku Prim's algorithm na anglickej Wikipedii.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Amdalhove pravidlo
Baud
Bloomov filter
Boolova algebra
Cardano (platforma)
Chomského hierarchia
Dijkstrov algoritmus
Eratostenovo sito
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk