Kruskalův algoritmus je účinný algoritmus pro konstrukci minimální kostry váženého spojeného neorientovaného grafu . Algoritmus se také používá k nalezení některých aproximací pro Steinerův problém [1] .
Algoritmus byl popsán Josephem Kraskalem v roce 1956 , tento algoritmus je téměř stejný jako Borůvkův algoritmus navržený Otakarem Borůvkou v roce 1926.
Zpočátku je aktuální sada hran nastavena na prázdnou. Poté, dokud je to možné, se provede následující operace: ze všech hran, jejichž přidání do již existující sady nezpůsobí v ní vznik cyklu, se vybere hrana s minimální hmotností a přidá se k již existující sadě . Když už takové hrany nejsou, algoritmus je hotový. Podgraf daného grafu obsahující všechny jeho vrcholy a nalezenou množinu hran je jeho minimální váhový strom . Podrobný popis algoritmu lze nalézt v literatuře [2] .
Před spuštěním algoritmu je nutné seřadit hrany podle hmotnosti, což trvá O(E × log(E)) čas. Poté je vhodné uložit spojené komponenty jako systém disjunktních sad . Všechny operace v tomto případě budou trvat O(E × α(E, V)) , kde α je funkce inverzní k Ackermannově funkci . Protože pro jakékoliv praktické problémy α(E, V) < 5 , pak to můžeme brát jako konstantu, takže celkovou dobu běhu Kruskalova algoritmu můžeme brát jako O(E * log(E)) .
Kruskalův algoritmus skutečně najde minimální hmotnostní kostru, protože jde o speciální případ Rado-Edmondsova algoritmu [3] pro grafický matroid , kde nezávislé množiny jsou acyklické množiny hran.
| obraz | Popis |
|---|---|
| Hrany AD a CE mají minimální hmotnost 5. Hrana AD se volí libovolně (na obrázku je zvýrazněna). Ve výsledku dostaneme množinu vybraných vrcholů ( A , D ). | |
| Nyní má hrana CE nejmenší váhu rovnou 5 . Protože přidání CE netvoří cyklus, zvolíme ji jako druhou hranu. Protože tato hrana nemá žádné společné vrcholy s existující množinou vybraných vrcholů ( A , D ), dostaneme druhou množinu vybraných vrcholů ( C , E ). | |
| Obdobně vybereme hranu DF , jejíž váha je rovna 6. V tomto případě nedojde k žádnému cyklu, jelikož mezi nevybranými neexistují hrany, které by měly oba vrcholy z jednoho ( A , D , F ) nebo z druhého ( C , E ) množina vybraných vrcholů . | |
| Další hrany jsou AB a BE s váhou 7. Hrana AB zvýrazněná na obrázku je vybrána náhodně. Tím se přidá vrchol B k první sadě vybraných vrcholů ( A , B , D , F ). Dříve nevybraná hrana BD je zvýrazněna červeně, protože její vrcholy jsou zahrnuty v množině vybraných vrcholů ( A , B , D , F ), a proto mezi B a D již existuje cesta (zelená) (pokud toto byly vybrány hrany, poté cyklus ABD ).
Další hranu lze vybrat až po nalezení všech cyklů. | |
| Podobně se vybere hrana BE s váhou 7. Protože tato hrana má vrcholy v obou množinách vybraných vrcholů ( A , B , D , F ) a ( C , E ), jsou tyto množiny sloučeny do jedné ( A , B C , D , E , F ) . V této fázi je červeně zvýrazněno mnohem více hran, protože množiny vybraných vrcholů a tedy množiny vybraných hran se sloučily. Nyní BC vytvoří cyklus BCE , DE vytvoří cyklus DEBA a FE vytvoří cyklus FEBAD . | |
| Algoritmus končí přidáním hrany EG s váhou 9. Počet vybraných vrcholů ( A , B , C , D , E , F , G ) = 7 odpovídá počtu vrcholů v grafu. Minimální kostra byla vytvořena. |
| Algoritmy pro vyhledávání grafů | ||
|---|---|---|
| Neinformované metody | ||
| Informované metody | ||
| Zkratky | ||
| Minimální kostra | ||
| jiný | ||