Kruskalov algoritmus

Kruskalov algoritmus, pomenovaný podľa Josepha Kruskala, je optimalizačný grafový algoritmus na hľadanie minimálnej kostry súvislého neorientovaného grafu s ohodnotením hrán, ktorý pri hľadaní riešenia uplatňuje pažravú stratégiu.

Vstupom algoritmu je súvislý graf  s daným ohodnotením hrán a výstupom je podmnožina hrán  taká, že graf  je strom, ktorý má spomedzi všetkých takýchto stromov najmenší súčet ohodnotení hrán.

Opis algoritmu 
 Vstup: súvislý graf  s daným ohodnotením hrán.
 Výstup: podmnožina hrán  taká, že graf  je minimálna kostra grafu G.
 Algoritmus: 
Inicializuj množinu A na prázdnu množinu.
Inicializuj množinu S na množinu všetkých hrán E.
Ak je množina S prázdna alebo je graf  strom, ukonči vykonávanie. Inak pokračuj krokom 4.
Odober z množiny S hranu e s minimálnym ohodnotením (ak ich je viac, vyber ľubovoľnú z nich). Pokiaľ hrana e spája dva rôzne komponenty súvislosti grafu , pridaj hranu e do množiny A. Pokračuj krokom 3.

Príklad

Pozri aj 
 Primov algoritmus

Zdroje 
 Cormen, T. H., Leiserson, Ch. E., Rivest, R. L., Stein, C.: Introduction to Algorithms. MIT Press, 2001.

Externé odkazy 
 Impementácia Kruskalovho algoritmu  v jazykoch C++ a Java .
 Kruskalov algoritmus .

Grafové algoritmy