Borůvkův algoritmus

Borůvkův algoritmus slouží k nalezení minimální kostry grafu (kostry takové, že je součet vah jejích hran minimální). Byl vymyšlen českým matematikem Otakarem Borůvkou za účelem nalezení efektivního trasování elektrické sítě na Moravě. Algoritmus byl později několikrát znovuobjeven (mezi jinými M. Sollinem), proto se o něm lze dočíst také jako o Sollinově algoritmu.

Princip

Borůvkův algorimus funguje na principu skládání komponent. Na začátku jsou všechny uzly grafu považovány za samostatné komponenty. Algoritmus v každém svém kroku propojí každou komponentu s jinou komponentou pomocí nejkratší možné hrany. Jelikož Borůvkův algoritmus vyžaduje, aby měly všechny hrany unikátní váhu, tak při propojení komponent nikdy nemůže vzniknout cyklus. Dále je zajištěno, že se v každém kroku zmenší počet komponent minimálně na polovinu - tj. algoritmus terminuje v $\\log_{2} \\vert U \\vert$ krocích. Při každém z těchto kroků je třeba najít pro všechny komponenty nejkratší vycházející hranu, což může zabrat až $O(\\vert H \\vert)$ operací. Celková asymptotická složitost Borůvkova algoritmu je tedy $O(|H| \\cdot \\log_{2} \\vert U \\vert)$ ).

Paralelizace algoritmu

Významnou výhodou Borůvkova algoritmu je snadná paralelizace spojování jednotlivých komponent řešení. Protože vyhledávání nejlevnějších hran vycházejících z daných komponent je zcela nezávislé na stavu ostatních komponent, tak lze tyto podproblémy řešit na samostatných výpočetních jednotkách.

Kód

Pseudocode

 /**
  * Boruvkuv algoritmus
  * V teto podobe nesnese graf s dvema stejne ohodnocenymi hranami 
  * @param graph graf
  * @param weight vahy jednotlivych hran
  * @return minimalni kostra   
  */
 boruvkaAlgorithm(graph, weight)
     SpanningTree tree //kostra
     components = graph.vertices //na pocatku jsou vrcholy nepospojovany
     while components.size > 1 do
         for each component in components //pro vsechny komponenty
             edge e = connectWithMinimalEdge(component, weight) //propojime s jinou komponentou pomoci minimalni hrany
             tree.add(e) //hranu pridame do kostry
     return tree

Princip

Paralelizace algoritmu

Kód

Doporučujeme