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 $G=(V,E)$ s daným ohodnotením hrán a výstupom je podmnožina hrán $A\subseteq E$ taká, že graf $G=(V,A)$ je strom, ktorý má spomedzi všetkých takýchto stromov najmenší súčet ohodnotení hrán.

Opis algoritmu

• Vstup: súvislý graf $G=(V,E)$ s daným ohodnotením hrán.
• Výstup: podmnožina hrán $A\subseteq E$ taká, že graf $G=(V,A)$ je minimálna kostra grafu G.
• Algoritmus:

1. Inicializuj množinu A na prázdnu množinu.
2. Inicializuj množinu S na množinu všetkých hrán E.
3. Ak je množina S prázdna alebo je graf $(G,A)$ strom, ukonči vykonávanie. Inak pokračuj krokom 4.
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 $(G,A)$, pridaj hranu e do množiny A. Pokračuj krokom 3.

Príklad

Obrázok	Opis
	Graf zo vstupu algoritmu. Čísla pri hranách znamenajú ich ohodnotenie. Hrany z množiny A budú označované zelenou farbou, hrany z množiny S budú označované čiernou farbou a ostatné hrany budú označované červenou farbou.
	AD 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.
	Hranou 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.
	Ďalej bola z rovnakého dôvodu do množiny A pridaná hrana DF s ohodnotením 6.
	Hranami 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.
	Algoritmus 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.
	Algoritmus 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.
• Tento článok je čiastočný alebo úplný preklad článku Kruskal's algorithm na anglickej Wikipédii.

Externé odkazy

• Impementácia Kruskalovho algoritmu Archivované 2010-08-25 na Wayback Machine v jazykoch C++ a Java (po anglicky).
• Kruskalov algoritmus (po anglicky).