Kruskal vs Prim
V informatike sú Primove a Kruskalove algoritmy nenásytným algoritmom, ktorý nájde minimálnu kostru pre spojený vážený neorientovaný graf. Kostra je podgraf grafu tak, že každý uzol grafu je spojený cestou, ktorou je strom. Každý kostra má váhu a minimálna možná hmotnosť/cena všetkých kostrov je minimálna kostra (MST).
Viac o Primovom algoritme
Algoritmus vyvinul český matematik Vojtěch Jarník v roku 1930 a neskôr nezávisle počítačový vedec Robert C. Prim v roku 1957. Znovu ho objavil Edsger Dijkstra v roku 1959. Algoritmus možno rozdeliť do troch kľúčových krokov;
Vzhľadom na spojený 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 hmotnosti každej hrany spojenej s uzlami v strome a vyberte minimum. Pridajte hranu a uzol na druhom konci stromu T a odstráňte hranu z grafu. (Vyberte ľubovoľné, ak existujú dve alebo viac minimál)
3. Opakujte krok 2, kým sa do stromu nepridá n-1 hrán.
Pri tejto metóde strom začína jedným ľubovoľným uzlom a každým cyklom sa od tohto uzla rozširuje. Preto, aby algoritmus správne fungoval, graf musí byť súvislý graf. Základná forma Primovho algoritmu má časovú zložitosť O(V2).
Viac o Kruskalovom algoritme
Algoritmus vyvinutý Josephom Kruskalom sa objavil v zborníku Americkej matematickej spoločnosti v roku 1956. Kruskalov algoritmus možno vyjadriť aj v troch jednoduchých krokoch.
Vzhľadom na graf s n uzlami a príslušnou hmotnosťou každej hrany, 1. Vyberte oblúk s najmenšou váhou celého grafu a pridajte ho do stromu a odstráňte z grafu.
2. Zo zostávajúcich vyberte najmenej váženú hranu spôsobom, ktorý netvorí cyklus. Pridajte okraj do stromu a odstráňte ho z grafu. (Vyberte ľubovoľné, ak existujú dve alebo viac minimál)
3. Zopakujte postup v kroku 2.
V tejto metóde algoritmus začína s najmenej váženou hranou a pokračuje vo výbere každej hrany v každom cykle. Preto v algoritme nemusí byť graf prepojený. 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 hranou.
• Primove algoritmy siahajú od jedného uzla k druhému, zatiaľ čo Kruskalov algoritmus vyberá hrany tak, že poloha hrany nie je založená na poslednom kroku.
• V primovom algoritme musí byť graf spojený grafom, zatiaľ čo Kruskalov môže fungovať aj na nesúvislých grafoch.
• Primov algoritmus má časovú zložitosť O(V2) a Kruskalov časovú zložitosť je O(logV).
