Borůvkův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Borůvkův algoritmus je algoritmus pro nalezení minimální kostry v grafu, jehož hrany mají různé (prosté) a kladné ohodnocení.

Historie[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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ě log_2 N, kde N je počet vrcholů grafu.

Implementace v pseudokódu[editovat | editovat zdroj]

  • Mějme souvislý graf G s hranami různé váhy a s prázdnou množinou hran T
  • Dokud tvoří vrcholy G spojené hranami z T alespoň dvě komponenty souvislosti:
    • Mějme prázdnou množinu hran E
    • Pro všechny komponenty souvislosti:
      • Mějme prázdnou množinu hran S
      • Pro všechny vrcholy z komponenty:
        • Přidejme nejlevnější hranu z vrcholu směřující do jiné komponenty do S
      • Přidejme nejlevnější hranu z S do E
    • Přidejme výslednou množinu hran E do T
  • Množina T je minimální kostra grafu G

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[editovat | editovat zdroj]

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)