Borůvka's algorithm is used to find the minimum/maximum spanning tree in the given graph (a spanning tree, in which is the sum of its edges weights minimal/maximal). The algorithm was developed in 1926 by Czech mathematician Otakar Borůvka, when he was trying to find an optimal routing for the electrical grid in Moravia. Because the algorithm was later several times reinvented (among others by M. Sollin), the procedure is also sometimes called Sollin's algorithm.
Description
The Borůvka's algorithm is based on merging of disjoint components. At the beginning of the procedure each vertex is considered as a separate component. In each step the algorithm connects (merges) every component with some other using strictly the cheapest outgoing edge of the given component (every edge must have a unique weight). This way it is guaranteed that no cycle may occur in the spanning tree.
Because every step connects at least half of the currently unconnected components, it is clear that the algorithm terminates in steps. Because each step takes up to
operations to find the cheapest outgoing edge for all the components, the asymptotic complexity of Borůvka's algorithm is
.
Parallelization of the algorithm
A significant advantage of the Borůvka's algorithm is that is might be easily parallelized, because the choice of the cheapest outgoing edge for each component is completely independent of the choices made by other components.
Code
/**
* Boruvka's algorithm
*
* @param graph graph (each edge has a different weight)
* @param weight weights of all the edges
* @return minimal spanning tree
*/
boruvkaAlgorithm(graph, weight)
SpanningTree tree //spanning tree
components = graph.vertices //at the beginning every vertex is a component
while components.size > 1 do
for each component in components
edge e = connectWithMinimalEdge(component, weight) //connect with some other component using a minimal edge
tree.add(e) //add the edge into the spanning tree
return tree