Kruskal vs Prim
Ve výpočetní technice jsou Primovy a Kruskalovy algoritmy chamtivý algoritmus, který najde minimální kostru pro připojený vážený neorientovaný graf. Překlenovací strom je podgrafem grafu, takže každý uzel grafu je spojen cestou, kterou je strom. Každý kostra má váhu a minimální možná váha / cena všech koster je minimální kostra (MST).
Více o Primově algoritmu
Algoritmus vyvinul český matematik Vojtěch Jarník v roce 1930 a později samostatně počítačový vědec Robert C. Prim v roce 1957. Znovu ho objevil Edsger Dijkstra v roce 1959. Algoritmus lze konstatovat ve třech klíčových krocích;
Vzhledem k připojenému grafu s n uzly a příslušné hmotnosti každé hrany, 1. Vyberte libovolný uzel z grafu a přidejte jej do stromu T (který bude prvním uzlem)
2. Zvažte váhy každé hrany připojené k uzlům ve stromu a vyberte minimum. Přidejte hranu a uzel na druhém konci stromu T a odeberte hranu z grafu. (Vyberte libovolné, pokud existují dvě nebo více minim.)
3. Opakujte krok 2, dokud do stromu nepřidáte n-1 hran.
V této metodě strom začíná jedním libovolným uzlem a od tohoto uzlu se rozšiřuje každým dalším cyklem. Aby tedy algoritmus správně fungoval, musí být graf spojeným grafem. Základní forma Primova algoritmu má časovou složitost O (V 2).
Více o Kruskalově algoritmu
Algoritmus vyvinutý Josephem Kruskalem se objevil ve sborníku Americké matematické společnosti v roce 1956. Kruskalův algoritmus lze také vyjádřit ve třech jednoduchých krocích.
Vzhledem k grafu s n uzly a příslušnou váhou každé hrany, 1. Vyberte oblouk s nejmenší váhou celého grafu a přidejte jej do stromu a vymažte z grafu.
2. Ze zbývajících vyberte nejméně váženou hranu způsobem, který netvoří cyklus. Přidejte hranu do stromu a odstraňte ji z grafu. (Vyberte libovolné, pokud existují dvě nebo více minim.)
3. Opakujte postup v kroku 2.
V této metodě začíná algoritmus s nejméně váženou hranou a pokračuje ve výběru každé hrany v každém cyklu. V algoritmu proto nemusí být graf připojen. Kruskalův algoritmus má časovou složitost O (logV)
Jaký je rozdíl mezi Kruskalovým a Primovým algoritmem?
• Primův algoritmus se inicializuje uzlem, zatímco Kruskalův algoritmus se inicializuje hranou.
• Primovy algoritmy se rozprostírají z jednoho uzlu do druhého, zatímco Kruskalův algoritmus vybírá hrany tak, aby poloha hrany nevycházela z posledního kroku.
• V primově algoritmu musí být graf spojeným grafem, zatímco Kruskalův může fungovat i na odpojených grafech.
• Primův algoritmus má časovou složitost O (V 2) a Kruskalova časová složitost je O (logV).
