Borůvkův algoritmus

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ě.[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.

Reference

V tomto článku byl použit překlad textu z článku Borůvka's algorithm na anglické Wikipedii.

  1. ↑ BORŮVKA, Otakar. O jistém problému minimálním. [s.l.]: Práce mor. přírodověd. spol. v Brně III (česky, shrnutí v němčině) 
  2. ↑ BORŮVKA, Otakar. Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí. [s.l.]: Elektronický Obzor, 1926. 
  3. ↑ CHOQUET, Gustave. Étude de certains réseaux de routes. [s.l.]: [s.n.], 1938. (francouzsky) 

Externí odkazy

Média použitá na této stránce

Boruvka's algorithm (Sollin's algorithm) Anim.gif
Autor: Alieseraj, Licence: CC BY-SA 3.0
An animation, describing Boruvka's (Sollin's) algorithm, for finding a minimum spanning tree in a graph - An example on the runtime of the algorithm