Kruskalův algoritmus

Kruskalův algoritmus (v České republice se někdy mylně zaměňuje s Borůvkovým algoritmem, ten ale funguje odlišně) je jeden z algoritmů využívaných v teorii grafů k nalezení minimální kostry grafu, jehož hrany mají nezáporné ohodnocení (délku). U souvislého grafu hledá podmnožinu hran, která tvoří strom obsahující všechny uzly, s tím, že celková váha (součet délek) hran grafu je minimální. V případě grafu o více komponentách, algoritmus hledá les minimálních koster, tedy minimální kostru každé komponenty. Kruskalův algoritmus je příkladem hladového algoritmu.

Historie

Algoritmus byl poprvé publikován Josephem B. Kruskalem, zaměstnancem Bellových Laboratoří, v roce 1956. Kruskal v úvodu své práce odkazuje na článek Otakara Borůvky, který pojednává o existenci jediné minimální kostry pro graf s hranami ohodnocenými různými nezápornými čísly.

Kruskal svůj algoritmus popsal následujícím způsobem:

Postup A:

• Opakuj následující kroky, dokud je to možné:
• Z hran grafu $G$, které dosud nebyly vybrány, vyber nejkratší hranu, která nevytváří žádnou kružnici s hranami již vybranými.
• Množina vybraných hran je kostrou grafu $G$, která je navíc minimální

V roce 1957 tento algoritmus popsali Loberman a Weinberger, těsně před zveřejněním se autoři o Kruskalově práci dověděli, kvůli detailnějšímu popisu problému a obecnější formulaci však svou práci publikovali.

Ve své práci Kruskal zmiňuje variaci postupu A, ve kterém se opakovaně odebírá nejdelší hrana z grafu, která ještě nezpůsobí rozpad grafu na více podgrafů. Tímto ekvivalentním postupem můžeme také vytvořit minimální kostru grafu.

Postup A':

• Opakuj následující kroky, dokud je to možné:
• Z hran $G$, které dosud nebyly vybrány, vyber nejdelší, která je nerozpojí.
• Množina nevybraných hran je minimální kostrou grafu $G$.

Tento alternativní postup byl v roce 1961 nezávisle popsán A. Kotzigem.

Postup B:

Jako obecnější postup pro podmnožinu uzlů grafu formuloval Kruskal postup B:

• Nechť V je libovolná pevná (neprázdná) podmnožina uzlů grafu $G$, potom opakuj následující kroky, dokud je to možné:
• Z hran grafu $G$, které dosud nebyly vybrány, ale jsou spojeny s uzlem z $V$ nebo s hranou grafu, která již byla vybrána, vyber nejkratší hranu, která nevytváří kružnice s hranami již vybranými.
• Množina vybraných hran je kostrou grafu $G$, která je navíc minimální. V případě, že $V$ je množina všech vrcholů grafu $G$, stává se z obecnějšího postupu B postup A.

Kruskal se ve své práci také zamýšlí nad existencí „duálního“ postupu k B, stejně jako je tomu v případě postupů A a A'. Požadovanou formulaci přináší Rosenstiehl v roce 1967.

První, kdo formuloval postup B byl Vojtěch Jarník v roku 1930, obvykle je přisuzován Robertu Primovi, který formuloval obecně kategorii těchto algoritmů, z výpočtového hlediska, ale preferoval (stejně jako později Edsger Dijkstra) použití postupu B.

Kruskalův původní důkaz předpokládá různé ohodnocení hran grafu.

Algoritmus

Ekvivalentně můžeme algoritmus popsat tak, že se vždy vybírá taková hrana, která má ze všech možných hran spojujících dva různé podstromy ve vytvářené kostře tu nejmenší váhu.

• vytvoř les $F$ (množinu stromů), ve kterém je každý uzel grafu samostatným podstromem
• vytvoř množinu $S$ obsahující všechny hrany grafu
• dokud je množina $S$ neprázdná
  • z množiny $S$ odeber hranu s minimální váhou
  • pokud tato hrana spojuje dva různé podstromy, přidej ji do lesa $F$, tak že tyto podstromy sluč do jednoho
  • v jiném případě hranu zahoď

Po skončení běhu algoritmu obsahuje les jedinou komponentu, tvořící minimální kostru grafu.

Složitost

Časová složitost závisí na způsobu implementace řazení a operací s množinovým rozkladem. Pro graf $G$ s počtem uzlů $U$ a hran $H$ je složitost algoritmu $O(U\log U)$, což je asymptoticky ekvivalentní s $O(H\log U)$. Hrany seřadíme některým z řadících algoritmů podle vah v čase $O(H\log H)$, to umožní algoritmu odstranit hranu s minimální vahou v konstantním čase. Pro zaznamenání informací příslušnosti uzlů k jednotlivým komponentám využijeme datovou strukturu disjoint-set (viz Disjoint-set data structure). V této datové struktuře můžeme pro vyhledávání a spojování (sjednocení) využít union-find, které mají složitost $O(U)$. Algoritmus udělá pro každou hranu dvě operace vyhledávání a jednu operaci sjednocení. I jednodušší datové struktury umožňují dosáhnout celkovou složitost $O(H\log H)=O(H\log U)$. Pokud jsou hrany již seřazeny, nebo je dokážeme seřadit v lineárním čase, může pomocí sofistikovanějších datových struktur dosáhnout složitost $O(H\alpha (U))$, kde $\alpha$ je inverzní Ackermannova funkce.

Příklad

	Původní ohodnocený graf. Čísla poblíž hran označují jejich cenu. Žádná hrana zatím není označena.
	AD a CE jsou hrany s nejmenší délkou. Můžeme zvolit libovolnou z dvou hran. Označíme hranu AD.
	Nejkratší neoznačenou hranou je CE s délkou 5. Označíme hranu CE.
	Nejkratší neoznačenou hranou je DF s délkou 6. Označíme hranu DF.
	Následující nejkratší hranou jsou AB a BE s délkou 7. Vybereme hranu AB. Hranu BD označíme červeně, protože mezi B a D již existuje cesta označená zelenou barvou, přidání hrany BD do výběru by způsobilo vznik nežádoucí kružnice ABD.
	Proces pokračuje označením následující nejkratší hrany BE. Tři hrany jsou následně označené červeně, protože BC by mohla vytvořit kružnici BCE, DE kružnici DEBA a FE kružnici FEBAD.
	Hledání minimální kostry končí přidáním hrany EG. Následující výběr jakékoliv jiné hrany by způsobil vznik kružnice a výsledek by již nebyl kostrou grafu.

Důkaz správnosti

Bez újmy na obecnosti můžeme graf považovat za úplný. Pokud by byl graf neúplný, jednoduše nahradíme hrany, které jsou jeho doplňkem do úplného grafu, za hrany s neporovnatelně větším ohodnocením.

Důkaz se skládá ze dvou částí. První dokazuje, že algoritmus na výstupu skutečně vytvoří kostru. Druhá část důkazu je potvrzením, že kostra je skutečně minimální.

Důkaz vytvoření kostry

Nechť $P$ je souvislý graf s ohodnocenými hranami a $Y$ je podgrafem $P$ vytvořeným Kruskalovým algoritmem. $Y$ nemůže obsahovat kružnici, protože poslední hrana přidána do kružnice by spojovala ten samý podstrom a ne dva rozdílné, co je podmínkou pro přidání nové hrany. $Y$ nemůže být nesouvislý, protože hrany přidané do $Y$ slučující podstromy byly do $Y$ přidány, z toho plyne, že $Y$ je kostrou grafu $P$.

Důkaz minimální kostry

Provedeme důkaz sporem. Nechť $Y$ je kostrou, ale ne minimální, zkoumaného grafu a $Y_{1}$ minimální kostrou grafu, která má nejmenší počet takových hran, které se nenacházejí v $Y$. Nechť $e$ je hrana, která by byla jako první přidána algoritmem do $Y$, z těch které nejsou v $Y_{1}$. $Y_{1}\cup {e}$ tvoří kružnici. Jelikož $Y$ je strom, nemůže obsahovat kružnici. Proto musí zmíněné sjednocení obsahovat hranu $f$, která v $Y$ není obsažena. $Y_{2}=Y_{1}\cup {e}\setminus {f}$ je také kostrou grafu a jeho celkové ohodnocení nemůže být menší než ohodnocení $Y_{1}$, proto $e$ nemůže mít menší ohodnocení než $f$. Dalším využitím důkazu sporem dokážeme, že ohodnocení hrany $f$ nemůže být menší než ohodnocení hrany $e$. Předpokládejme opak ($f$ má menší ohodnocení jako $e$) a pamatujme, že hrany mají být přidány do $Y$ v pořadí jejich neklesajících ohodnocení. Proto by bylo $f$ testováno pro přidání do podlesu $Y_{3}\subset Y\cap Y_{1}$ před $e$ ($e$ je první hrana $Y$, která není v $Y_{1}$). Hrana $f$ ale nevytvoří kružnici v $Y_{1}$, proto nemůže vytvořit ani kružnici v $Y_{3}$ a byla by přidána do vytvářeného stromu. Z předchozích úvah plyne, že ohodnocení $e$ a $f$ jsou stejné a $Y_{2}$ je minimální kostrou, ale $Y_{2}$ má o jednu společnou hranu s $Y$ víc, než má $Y_{1}$, co je ve sporu s výběrem $Y_{1}$ za minimální kostru grafu.

Pseudokód

1 Kruskal(G,w)
2 A := ∅ Vybraná kostra zatím prázdná,
3     for každý uzel u ∈ U //pro každý uzel se vytvoří samostatný podstrom
4         do MAKE-SET(u) 
5   uspořádej H do neklesající posloupnosti podle váhy w
6   for každou hranu [u, v] ∈ H v pořadí neklesajících vah
7     do if FIND-SET(u) != FIND-SET(v) //Hrana [u, v] je vhodná, přidej ji do kostry a spoj odpovídající podstromy
8         then A := A ∪ {[u, v]} 
9             UNION(u, v)
10  return A

Odkazy

Externí odkazy

• Obrázky, zvuky či videa k tématu Kruskalův algoritmus na Wikimedia Commons
• Animace Kruskalova algoritmu
• Bludiště pro Kruskalův a Primů algoritmus
• Zdrojové kódy (C++) s dokumentací

Literatura

• GRAHAM, Ronald Lewis; HELL, Pavol. On the History of the Minimum Spanning Tree Problem. Annals of the History of Computing, IEEE. 12. leden-březen 1985, roč. 7, čís. 1, s. 43–57. Dostupné online [PDF]. ISSN 1058-6180. DOI 10.1109/MAHC.1985.10011. (anglicky) 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574. (anglicky)
• KOLÁŘ, Josef. Teoretická informatika. Praha: Česká informatická společnost, 2004. ISBN 80-900853-8-5. Kapitola 5, s. 102.