Primov algoritmus: Rozdiel medzi revíziami
→Popis: preklepy |
→Príklad: preklepy |
||
Riadok 20: | Riadok 20: | ||
|- |
|- |
||
|[[Image:Prim Algorithm 1.svg|200px]] |
|[[Image:Prim Algorithm 1.svg|200px]] |
||
| |
|Z grafu vyberieme ľubovoľný vrchol. V tomto prípade vrchol '''D'''. Tým nám vznikne podgraf. Vrcholy '''A''', '''B''', '''E''' a '''F''' sú susednými vrcholmi '''D''', teda sú s ním spojené hranou. Vrchol '''A''' je od vrcholu '''D''' vzdialený najmenej a bude vybraný ako druhý vrchol, spolu s hranou '''AD'''. |
||
|- |
|- |
||
|[[Image:Prim Algorithm 2.svg|200px]] |
|[[Image:Prim Algorithm 2.svg|200px]] |
Verzia z 15:03, 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 obsahujúci všetky vrcholy pôvodného grafu a súčet ohodnotenia hrán z tejto množiny je minimálny. 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