Rozdiel medzi Kruskal a Prim

Kruskal vs Prim

V počítačovej vede sú Primove a Kruskalove algoritmy chamtivý algoritmus, ktorý nájde minimálny preklenovací strom pre pripojený vážený nepriamy graf. Spanning tree je podgraf grafu tak, že každý uzol grafu je spojený cestou, ktorou je strom. Každý preklenovací strom má hmotnosť a minimálna možná hmotnosť / cena všetkých preklenovacích stromov je minimálny preklenovací strom (MST)..

Viac o Primovom algoritme

Algoritmus bol vyvinutý českým matematikom Vojtěchom Jarníkom v roku 1930 a neskôr nezávisle počítačovým vedcom Robertom C. Primom v roku 1957. V roku 1959 ho objavil Edsger Dijkstra. Algoritmus možno uviesť v troch kľúčových krokoch;

Vzhľadom na pripojený graf s uzlami a príslušnú hmotnosť každej hrany,

1. Vyberte ľubovoľný uzol z grafu a pridajte ho do stromu T (ktorý bude prvým uzlom).

2. Zvážte hmotnosť každej hrany pripojenej k uzlom v strome a vyberte minimum. Pridajte okraj a uzol na druhý koniec stromu T a odstráňte okraj z grafu. (Vyberte ľubovoľné, ak existujú dve alebo viac minimálnych hodnôt)

3. Opakujte krok 2, až kým sa do stromu nepridajú hrany n-1.

V tejto metóde strom začína jedným ľubovoľným uzlom a rozširuje sa od tohto uzla s každým cyklom ďalej. Preto, aby algoritmus pracoval správne, musí byť grafom pripojený graf. Základná forma Primovho algoritmu má časovú zložitosť O (V²).

Viac o Kruskalovom algoritme

Algoritmus vyvinutý Josephom Kruskalom sa objavil v zborníku American Mathematical Society v roku 1956. Kruskalov algoritmus možno vyjadriť v troch jednoduchých krokoch.

Vzhľadom na graf s uzlami a príslušnú hmotnosť každej hrany,

1. Vyberte oblúk s najmenšou hmotnosťou celého grafu, pridajte ho do stromu a vymažte z grafu.

2. Zo zvyšku vyberte najmenej váženú hranu tak, aby nevytvorila cyklus. Pridajte okraj do stromu a odstráňte z grafu. (Vyberte ľubovoľné, ak existujú dve alebo viac minimálnych hodnôt)

3. Zopakujte postup v kroku 2.

V tejto metóde algoritmus začína s najmenšou hranou a pokračuje v 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 začína hranou.

• Primove algoritmy sa rozprestierajú od jedného uzla k druhému, zatiaľ čo Kruskalov algoritmus vyberie hrany tak, aby poloha hrany nebola založená na poslednom kroku.

• Podľa primovho algoritmu musí byť graf prepojeným grafom, zatiaľ čo Kruskalova funkcia môže fungovať aj na odpojených grafoch.

• Primov algoritmus má časovú zložitosť O (V²) a Kruskalova časová zložitosť je O (logV).