Rozdíl mezi Kruskal a Prim

Kruskal vs Prim

V počítačové vědě jsou Primovy a Kruskalovy algoritmy chamtivý algoritmus, který najde minimální rozpětí stromu pro připojený vážený nepřímý graf. Spanning tree je podgraf grafu tak, že každý uzel grafu je spojen cestou, kterou je strom. Každý překlenovací strom má váhu a minimální možná hmotnost / cena všech překlenovacích stromů je minimální překlenovací strom (MST).

Více o Primově algoritmu

Algoritmus byl vyvinut českým matematikem Vojtěchem Jarníkem v roce 1930 a později samostatně počítačovým vědcem Robertem C. Primem v roce 1957. Byl znovu objeven Edsgerem Dijkstrem v roce 1959. Algoritmus lze uvést ve třech klíčových krocích;

Daný připojený graf s uzly a příslušnou hmotností každé hrany,

1. Vyberte libovolný uzel z grafu a přidejte jej do stromu T (který bude prvním uzlem)

2. Zvažte hmotnosti každé hrany připojené k uzlům ve stromu a vyberte minimum. Přidáme hranu a uzel na druhý konec stromu T a odstraníme hranu z grafu. (Vyberte, pokud existují dvě nebo více minim)

3. Opakujte krok 2, dokud se do stromu nepřidají okraje n-1.

V této metodě strom začíná jediným arbitrárním uzlem a rozšiřuje se od tohoto uzlu s každým cyklem. Aby algoritmus správně fungoval, musí být grafem připojený graf. Základní forma Primova algoritmu má časovou složitost O (V²).

Více o Kruskalově algoritmu

Algoritmus vyvinutý Josephem Kruskalem se objevil v sborníku Americké matematické společnosti v roce 1956. Kruskalův algoritmus lze také vyjádřit ve třech jednoduchých krocích.

Daný graf s uzly a příslušnou hmotností každé hrany,

1. Vyberte oblouk s nejnižší hmotností celého grafu a přidejte jej do stromu a vymažte z grafu.

2. Ze zbývajícího vyberte nejméně váženou hranu tak, aby netvořila cyklus. Hranu přidejte do stromu a odstraňte z grafu. (Vyberte, pokud existují dvě nebo více minim)

3. Opakujte postup v kroku 2.

V této metodě algoritmus začíná s nejméně váženou hranou a pokračuje v výběru každé hrany v každém cyklu. Graf tedy nemusí být v algoritmu spojen. Algoritmus Kruskal 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 začíná hranou.

• Primovy algoritmy se rozpínají od jednoho uzlu k druhému, zatímco Kruskalův algoritmus vybírá hrany tak, aby pozice hrany nebyla založena na posledním kroku.

• V primově algoritmu musí být graf spojeným grafem, zatímco Kruskalovy grafy mohou fungovat i na odpojených grafech.

• Primův algoritmus má časovou složitost O (V²) a Kruskalova časová složitost je O (logV).