Borůvkův algoritmus
_Anim.gif)
Borůvkův algoritmus je algoritmus pro nalezení minimální kostry v grafu, jehož hrany mají různé (prosté) a kladné ohodnocení.
Historie
Poprvé byl publikován roku 1926 Otakarem Borůvkou jako metoda pro konstrukci efektivní elektrické sítě na Moravě.[1][2] Algoritmus byl znovuobjeven Gustavem Choquetem roku 1938,[3] poté znovu Florekem, Łukasiewiczem, Perkalem, Steinhausem a Zubrzyckim roku 1951 a ještě jednou v 60. letech Sollinem. Jelikož Sollin byl z předcházejícího výčtu jediným vědcem ze západu, algoritmus je často označován jako Sollinův algoritmus, především v literatuře týkající se paralelního zpracování dat.
Algoritmus
Algoritmus pracuje tak, že postupně spojuje komponenty souvislosti (na počátku je každý vrchol komponentou souvislosti) do větších a větších celků, až zůstane jen jediný, a to je hledaná minimální kostra. V každé fázi vybere pro každou komponentu souvislosti hranu s co nejnižší cenou, která směřuje do jiné komponenty souvislosti a tu přidá do kostry. V každé fázi se počet komponent souvislosti sníží nejméně dvakrát, počet fází bude tedy maximálně , kde N je počet vrcholů grafu.
Implementace v pseudokódu
algoritmus Borůvka:
vstup: Graf G jehož hrany mají různé ohodnocení.
výstup: Strom F je minimální kostra grafu G.
Inicializuj les F jako množinu stromů s jedním vrcholem pro každý vrchol v grafu.
dokud má F více než jednu komponentu:
Najdi komponenty souvislosti v F a označ každý vrchol G jeho komponentou
Inicializuj nejlevnější hranu pro každou komponentu na speciální hranu s cenou ∞
pro každou hranu uv v G:
pokud mají u a v různé označení komponenty:
pokud je uv levnější než nejlevnější hrana pro komponentu u:
Nastav uv jako nejlevnější hranu pro komponentu u
pokud uv je levnější než nejlevnější hrana pro komponentu v:
Nastav uv jako nejlevnější hranu pro komponentu v
pro každou komponentu:
Přidej její nejlevnější hranu do F
Je možné ukázat, že asymptotická časová složitost Borůvkova algoritmu je O(M log N), kde N je počet vrcholů a M počet hran grafu.