Borůvkův algoritmus

Z Wikipedie, otevřené encyklopedie

Algoritmy hledající minimální kostru grafu Jarníkův algoritmus Borůvkův algoritmus Kruskalův algoritmus

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

Obsah 1 Historie 2 Algoritmus 2.1 Implementace v pseudokódu 3 Reference

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

[editovat] 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ě log₂N, kde N je počet vrcholů grafu.

[editovat] Implementace v pseudokódu

• Mějme souvislý grafem 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.

[editovat] Reference

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)

Tento článek je zčásti nebo zcela založen na překladu článku en:Borůvka's algorithm na anglické Wikipedii.