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 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ž operací. Celková asymptotická složitost Borůvkova algoritmu je tedy ).
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
01.
/**
02.
* Boruvkuv algoritmus
03.
* V teto podobe nesnese graf s dvema stejne ohodnocenymi hranami
04.
* @param graph graf
05.
* @param weight vahy jednotlivych hran
06.
* @return minimalni kostra
07.
*/
08.
boruvkaAlgorithm(graph, weight)
09.
SpanningTree tree
//kostra
10.
components = graph.vertices
//na pocatku jsou vrcholy nepospojovany
11.
while
components.size >
1
do
12.
for
each component in components
//pro vsechny komponenty
13.
edge e = connectWithMinimalEdge(component, weight)
//propojime s jinou komponentou pomoci minimalni hrany
14.
tree.add(e)
//hranu pridame do kostry
15.
return
tree