Kruskal vs Prim
V informatice jsou Primovy a Kruskalovy algoritmy chamtivým algoritmem, který najde minimální kostru pro připojený vážený neorientovaný graf. Kostra je podgraf grafu tak, že každý uzel grafu je spojen cestou, což je strom. Každý kostra má váhu a minimální možná hmotnost/cena všech kostry je minimální kostra (MST).
Více o Primově algoritmu
Algoritmus vyvinul český matematik Vojtěch Jarník v roce 1930 a později nezávisle počítačový vědec Robert C. Prim v roce 1957. Znovu jej objevil Edsger Dijkstra v roce 1959. Algoritmus lze rozdělit do tří klíčových kroků;
Za předpokladu, že spojený graf s n uzly a příslušnou váhou každé hrany, 1. Vyberte libovolný uzel z grafu a přidejte jej do stromu T (což bude první uzel)
2. Zvažte hmotnosti 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 nebude do stromu přidáno n-1 hran.
V této metodě strom začíná jedním libovolným uzlem a každým cyklem se od tohoto uzlu rozšiřuje. Proto, aby algoritmus správně fungoval, graf musí být souvislý graf. Základní forma Primova algoritmu má časovou složitost O(V2).
Více o Kruskalově algoritmu
Algoritmus vyvinutý Josephem Kruskalem se objevil ve sborníku American Mathematical Society v roce 1956. Kruskalův algoritmus lze také vyjádřit ve třech jednoduchých krocích.
Za předpokladu, že graf 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 odstraňte z grafu.
2. Ze zbývajících vyberte nejméně váženou hranu způsobem, který nevytváří cyklus. Přidejte okraj do stromu a odstraňte z grafu. (Vyberte libovolné, pokud existují dvě nebo více minim)
3. Opakujte proces v kroku 2.
V této metodě algoritmus začíná s nejméně váženou hranou a pokračuje ve výběru každé hrany v každém cyklu. Proto v algoritmu nemusí být graf propojen. 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í od jednoho uzlu k druhému, zatímco Kruskalův algoritmus vybírá hrany tak, že poloha hrany není založena na posledním kroku.
• V primově algoritmu musí být graf spojený graf, zatímco Kruskalův může fungovat i na nesouvislých grafech.
• Primův algoritmus má časovou složitost O(V2) a Kruskalova časová složitost je O(logV).
