Borůvkův algoritmus

Borůvkův algoritmus (nebo Borův-Sollinův algoritmus ) je algoritmus pro nalezení minimální kostry v grafu.

Poprvé ji publikoval v roce 1926 Otakar Borůvka jako metodu pro nalezení optimální elektrické sítě na Moravě . Byl několikrát znovu objeven, například Florek , Perkal a Sollin . Posledně jmenovaný byl navíc jediným západním vědcem na tomto seznamu, a proto je tento algoritmus často označován jako Sollinův algoritmus, zejména v literatuře o paralelních počítačích .

Algoritmus

Činnost algoritmu se skládá z několika iterací, z nichž každá spočívá v postupném přidávání hran do grafu zahrnujícího les , dokud se les nezmění ve strom , tedy les skládající se z jedné spojené komponenty.

Algoritmus lze popsat následovně:

1. Zpočátku nechť je prázdná množina hran (představující les, ve kterém je každý vrchol zahrnut jako samostatný strom).
2. Není ještě strom (což je ekvivalentní podmínce: zatímco počet hran v je menší než , kde je počet vrcholů v grafu):
   • Pro každou připojenou komponentu (tj. strom v rozprostřeném lese) v podgrafu s hranami najděte nejlevnější hranu spojující tuto komponentu s nějakou jinou spojenou komponentou. (Předpokládá se, že hmotnosti hran jsou různé, nebo nějak dodatečně objednané tak, aby bylo vždy možné najít jednu hranu s minimální hmotností).
   • Přidejte všechny nalezené hrany do sady .
3. Výsledná množina hran je minimální kostrou vstupního grafu.

Složitost algoritmu

Při každé iteraci je počet stromů v rozprostřeném lese alespoň poloviční, takže algoritmus celkem provede nejvíce iterací. Každá iterace může být implementována se složitostí , takže celková doba běhu algoritmu je čas (zde a počet vrcholů a hran v grafu, v tomto pořadí).

U některých typů grafů, zejména rovinných , však může být redukována na . [1] Existuje také randomizovaný minimální algoritmus spanning tree založený na Borůvkově algoritmu, který běží v průměru v lineárním čase.

Viz také

• Minimální kostra
• kostra
• Dijkstrův algoritmus
• Kruskalův algoritmus
• Algoritmus zpětného mazání
• Primův algoritmus

Literatura

• Sedgwick R. Základní algoritmy v C++, část 5. Algoritmy na grafech. ISBN 5-93772-082-2 .

Poznámky

1. ↑ Eppstein, David (1999), Spanning trees and spanners, in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry , Elsevier, str. 425–461  ; Mareš, Martin (2004), Dva lineární časové algoritmy pro MST na vedlejších uzavřených grafových třídách , Archivum mathematicum vol. 40 (3): 315–320 , < http://www.emis.de/journals/AM/04-3 /am1139.pdf > Archivováno 9. května 2009 na Wayback Machine .