Kruskal vs Prim
V informatike sú Primove a Kruskalove algoritmy chamtivým algoritmom, ktorý zistí minimálny rozsah stromu pre pripojený vážený neusmernený graf. Spanning tree je podgraf grafu tak, že každý uzol grafu je spojený cestou, ktorá je stromom. Každý spanning tree má váhu a minimálna možná váha / cena všetkých spanning tree je minimálny spanning tree (MST).
Viac o Primovom algoritme
Algoritmus vyvinul český matematik Vojtěch Jarník v roku 1930 a neskôr samostatne počítačový vedec Robert C. Prim v roku 1957. Znovu ho objavil Edsger Dijkstra v roku 1959. Algoritmus je možné určiť v troch kľúčových krokoch;
Vzhľadom na súvisiaci graf s n uzlami a príslušnou hmotnosťou každej hrany, 1. Vyberte ľubovoľný uzol z grafu a pridajte ho do stromu T (ktorý bude prvým uzlom)
2. Zvážte váhy každého okraja pripojeného k uzlom v strome a vyberte minimum. Pridajte hranu a uzol na druhom konci stromu T a vyberte hranu z grafu. (Vyberte, ak existujú dve alebo viac minimálnych hodnôt.)
3. Opakujte krok 2, kým sa k stromu nepridá n-1 hrán.
V tejto metóde strom začína jedným ľubovoľným uzlom a od tohto uzla sa rozširuje každým ďalším cyklom. Preto, aby algoritmus fungoval správne, musí byť graf prepojeným grafom. Základná forma Primovho algoritmu má časovú zložitosť O (V 2).
Viac o Kruskalovom algoritme
Algoritmus, ktorý vyvinul Joseph Kruskal, sa objavil v zborníku Americkej matematickej spoločnosti v roku 1956. Kruskalov algoritmus možno tiež vyjadriť v troch jednoduchých krokoch.
Vzhľadom na graf s n uzlami a príslušnou váhou každej hrany, 1. Vyberte oblúk s najmenšou hmotnosťou celého grafu a pridajte ho do stromu a odstráňte z grafu.
2. Zo zvyšných vyberte najmenej váženú hranu spôsobom, ktorý netvorí cyklus. Pridajte okraj k stromu a odstráňte ho z grafu. (Vyberte, ak existujú dve alebo viac minimálnych hodnôt.)
3. Opakujte postup v kroku 2.
V tejto metóde algoritmus začína od najmenej váženej hrany a pokračuje vo výbere každej hrany v každom cykle. Preto v algoritme nemusí byť graf pripojený. Kruskalov algoritmus má časovú zložitosť O (logV)
Aký je rozdiel medzi Kruskalovým a Primovým algoritmom?
• Primov algoritmus sa inicializuje uzlom, zatiaľ čo Kruskalov algoritmus sa inicializuje okrajom.
• Primove algoritmy sa rozprestierajú od jedného uzla k druhému, zatiaľ čo Kruskalov algoritmus vyberá hrany tak, aby poloha hrany nevychádzala z posledného kroku.
• Podľa primovho algoritmu musí byť graf pripojeným grafom, zatiaľ čo Kruskalove funkcie môžu fungovať aj na odpojených grafoch.
• Primov algoritmus má časovú zložitosť O (V 2) a Kruskalova časová zložitosť je O (logV).
