Kruskalov algoritmus

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

  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[upraviť | upraviť zdroj]

Obrázok Opis
Prim Algorithm 0.svg 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.
Kruskal Algorithm 1.svg 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.
Kruskal Algorithm 2.svg 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.
Kruskal Algorithm 3.svg Ďalej bola z rovnakého dôvodu do množiny A pridaná hrana DF s ohodnotením 6.
Kruskal Algorithm 4.svg 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.
Kruskal Algorithm 5.svg 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.
Kruskal Algorithm 6.svg 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[upraviť | upraviť zdroj]

Zdroje[upraviť | upraviť zdroj]

Externé odkazy[upraviť | upraviť zdroj]