Přejít na obsah messages.homepage.accessibility

Kruskalův algoritmus

1. Popis standardní metody algoritmu

Kruskalův algoritmus slouží k vyhledání minimální kostry grafu. Pracujeme s váženým neorientovaným grafem $G = (V, E, w)$, kde $V$ je množina vrcholů, $E$ je množina neorientovaných hran a $w$ je kladné ohodnocení hran.

  1. Na počátku algoritmu inicializujeme kostru $T = (V, \emptyset)$ obsahující všechny vrcholy grafu $G$ a prázdnou množinu hran.
  2. Seřadíme všechny hrany grafu $G$ vzestupně dle jejich ohodnocení a v tomto pořadí je postupně zpracováváme.
  3. Pokud přidáním konkrétní hrany $e$ do kostry $T$ nevniká kružnice, přidáme $e$ do $T$, v opačném případě hranu do $T$ nepřidáme.
  4. Po zpracování poslední hrany s nejvyšším ohodnocením získáme minimální kostru $T$.

Při běžném provedení algoritmu pracujeme s vizuální reprezentací grafu. Hrany, které přidáváme do kostry, zvýrazňujeme (barevně či jiným způsobem) přímo v zadaném grafu. Na Obrázku 1 je znázorněn graf $H$ o sedmi vrcholech. Je ukázána situace před zpracováním 4. hrany v pořadí, mezi uzly $D$$G$. Po prvních třech krocích se do kostry grafu vložily hrany $CF$, $DE$, $CD$. Jelikož přidáním hrany $DG$ nevytvoříme kružnici, můžeme ji taktéž vložit do kostry.

Příklad 1: Vážený neorientovaný graf $H$
Obrázek 1: Vážený neorientovaný graf $H$, ukázka zvýraznění hran kostry i aktuálně zpracovávané hrany

V dalším pokračování však do kostry grafu nemůžeme přidat ani jednu hranu s ohodnocením 4, protože jejich vložením by v obou případech vznikla kružnice délky 3 (mezi trojicí $C, D, F$ či $D, E, G$).

Pro názornost uvádíme i konkrétní příklad váženého neorientovaného grafu a Animaci 1 naznačující výpočet minimální kostry pomocí Kruskalova algoritmu.

Příklad 2: Vážený neorientovaný graf $H$
  •  
  •  
Animace 1: výpočet minimální kostry pomocí Kruskalova algoritmu

2. Návrh možných adaptací

1. Organizace hran grafu v tabulce podle vrcholů, zápis kostry do dalšího dokumentu (listu):

Graf je nabízen ve formě tabulky. Do jejího prvního sloupce zapisujeme návěští vrcholů. Do dalších buněk na stejném řádku pro daný vrchol $X$ vkládáme všechny hrany vycházející z $X$, a to ve formátu $X$$n$$Y$, kde $n$ je ohodnocení hrany a $Y$ je koncový vrchol hrany. $V$ dalším listu tabulky, případně v samostatném souboru, uchováváme hrany, které zařazujeme do minimální kostry. Taktéž tam evidujeme množiny uzlů, které jsou přidanými hranami propojeny. Uvažujme tentýž graf $H$ o sedmi uzlech, který jsme znázornili na Obrázku 1. Následující dvě tabulky (Tabulka 1Tabulka 2) zachycují stav po přidání prvních dvou hran do minimální kostry grafu $H$.

Příklad 3: Graf $H$Obrázku 1 po přidání dvou hran
$A$ $A$$5$$C$ $A$$6$$D$ $A$$7$$B$
$B$ $B$$5$$D$ $B$$6$$E$ $B$$7$$A$
$C$ $C$$3$$D$ $C$$5$$A$
$D$ $D$$3$$C$ $D$$3$$G$ $D$$4$$F$ $D$$5$$B$ $D$$6$$A$
$E$ $E$$4$$G$ $E$$6$$B$
$F$ $F$$4$$D$ $F$$7$$G$
$G$ $G$$3$$D$ $G$$4$$E$ $G$$7$$F$
Tabulka 1: Graf $H$ formou tabulky, stav po přidání prvních dvou hran $C$$2$$F$, $D$$2$$E$
Příklad 4: Kostra grafu $H$Obrázku 1 po přidání dvou hran
MKG – Hrany: $C$$2$$F$ $D$$2$$E$
MKG – Množiny vrcholů:
$C, F$
$D, E$
Tabulka 2: Prozatimní kostra grafu $H$, stav po přidání prvních dvou hran $C$$2$$F$, $D$$2$$E$

Z předchozích dvou tabulek je patrné, že obě dosud přidané hrany propojují množiny uzlů $ \{ C, F\}$ a $ \{ D, E\}$. Před přidáním další hrany v pořadí $(C$$3$$D)$ musíme ověřit, zda v kostře grafu $H$ nevznikne kružnice. Vidomý student provádí kontrolu vizuálně, nevidomý si k tomuto účelu eviduje množiny uzlů propojených hranami dosavadní kostry. Pokud oba vrcholy zpracovávané hrany patří do stejné množiny uzlů, jejím přidáním bychom vytvořili kružnici. $V$ opačném případě aktualizujeme Tabulku 3. Aktuální hranu vkládáme do kostry a následně upravíme množiny vzájemně propojených uzlů. Nesmíme zapomenout, že právě zpracovaná hrana byla v Tabulce 2 uvedena dvakrát, je tudíž nutné oba výskyty vymazat.

2. Organizace hran ve dvou sloupcích tabulky, zápis kostry do dalšího dokumentu (listu):

Graf je opět nabízen ve formě tabulky, hrany jsou však organizovány jiným způsobem. V 1. sloupci je jejich charakteristika, opět ve formátu $x$$n$$y$, kde $x, y$ označují uzly propojené hranou s ohodnocením $n$. Ve 2. sloupci je znovu zopakováno ohodnocení hrany. Ukázku tohoto způsobu organizace hran nabízíme v Tabulce 3 .

Příklad 5: Hrany grafu $H$Obrázku 1 včetně ohodnocení
$A$$5$$C$ $5$
$A$$6$$D$ $6$
$A$$7$$B$ $7$
$B$$5$$D$ $5$
$B$$6$$E$ $6$
$C$$2$$F$ $2$
$C$$3$$D$ $3$
$D$$2$$E$ $2$
$D$$3$$G$ $3$
$D$$4$$F$ $4$
$E$$4$$G$ $4$
$F$$7$$G$ $7$
Tabulka 3:Tabulková reprezentace grafu $G$Obrázku 1

Většina tabulkových procesorů nabízí možnost seřadit data podle hodnot určitého sloupce. Nevidomý student tedy může hrany seřadit vzestupně podle ohodnocení, když je uspořádá podle 2. sloupce. Pro zápis kostry grafu a množin dosud propojených uzlů používáme buď druhý list tabulky či samostatný dokument. Postupujeme stejným způsobem jako v předchozí metodě.

3. Diskuze nad výhodami a nevýhodami

Poznamenejme rovnou, že druhou adaptaci nevidomí studenti hodnotili shodně jako lepší. Měli pro to tři hlavní důvody:

  1. ihned našli hranu, kterou mají aktuálně zpracovat;
  2. strávili méně času přesunem kurzoru mezi řádky a sloupci tabulky;
  3. nemuseli každou zpracovanou hranu dvakrát mazat ze zadání grafu.

U první metody studenti obtížně hledali hranu s aktuálně nejmenším ohodnocením. Řešení může být následující. Hrany s nejmenším ohodnocením je možné vyhledat postupným zadáváním řetězců "–$1$–", "–$2$–", atd. Jeden ze studentů přišel s dalším nápadem, a to rezignovat na reprezentaci grafu formou tabulky a využít podobným způsobem běžný textový editor, v němž hrany pro daný uzel $x$ umístíme na samostatný řádek. Nevidomí studenti tak plně mohou využít užitečných klávesových zkratek pro práci s textem i možností brailleského řádku.