Borůvkův algoritmus

Technology

12 hours ago

Author

Animace popisující běh algoritmu - nalezení minimální kostry grafu. 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ě. Algoritmus byl znovuobjeven Gustavem Choquetem roku 1938, poté znovu Florekem, Łukasiewiczem, Perkalem, Steinhausem a Zubrzyckim roku 1951 a ještě jednou v 60. +more 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. +more V každé fázi se počet komponent souvislosti sníží nejméně dvakrát, počet fází bude tedy maximálně \log_2 N, 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.