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 
 Obrázok  Opis200pxGraf zo vstupu algoritmu. Čísla pri hranách znamenajú ich ohodnotenie. Hrany z množiny A budú označované , hrany z množiny S budú označované čiernou farbou a ostatné hrany budú označované .200pxAD a CE sú hrany v S s minimálnym ohodnotením. Algoritmus (náhodne alebo podľa ľubovoľného kritéria) vybral hranu AD. Keďže spája dva rôzne komponenty súvislosti, bola hrana AD pridaná do množiny A.200pxHranou v S s najmenším ohodnotením je v tomto prípade hrana CE. Keďže spája dva rôzne komponenty súvislosti, bola pridaná do A.200pxĎalej bola z rovnakého dôvodu do množiny A pridaná hrana DF s ohodnotením 6.200pxHranami v S s minimálnym ohodnotením sú hrany AB a BE (s ohodnotením 7). Algoritmus sa rozhodol pre výber hrany AB, ktorá spája dva rôzne komponenty súvislosti, a preto je pridaná do A. Hrana BD bola označená červenou farbou, keďže spája rovnaké komponenty súvislosti. Toto je správny alternatívny spôsob fungovania algoritmu (obzvlášť vhodný pri jeho manuálnom vykonávaní), ale treba mať na pamäti, že algoritmus tak ako bol opísaný vyššie, by hranu BD objavil a označil červenou farbou až neskôr.200pxAlgoritmus pridáva do A hranu BE s ohodnotením 7, pričom červenou farbou označuje viacero hrán: BC, pretože by utvorila kružnicu BCE,  DE, pretože by utvorila kružnicu DEBA a FE, pretože by utvorila kružnicu FEBAD.200pxAlgoritmus končí pridaním hrany EG s ohodnotením 9 do množiny A. Hrany označené zelenou farbou tvoria minimálnu kostru grafu.

 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 .

Kategória:Grafové algoritmy
Kategória:Eponymické termíny v informatike