Borůvka's algorithm

The algorithm of Borůvka is considered the first algorithm for finding minimum spanning trees in undirected graphs. He was described in 1926 by the Czech mathematician Otakar Borůvka. The two well-known algorithms for solving this problem, the algorithm of primary and Kruskal 's algorithm. In the first publication of these two algorithms Borůvka is mentioned in each case.

Rationale and complexity

Like the algorithm of Kruskal 's algorithm starts Borůvka with many sub- frames, each consisting of a node, the node set V of the graph G = (V, E). In each iteration that follows a shortest edge of a frame part is wanted to another. The selection of these edges may be done in particular in the possibility of parallel execution simultaneously, which makes the algorithm more attractive to parallel implementations. The so part connected frameworks are merged into one part each scaffold. At each iteration, is halved in this manner, the number of sub- frames, so the algorithm terminates in a maximum of log n phases. Since the selection of the shortest edge before a sorting method must be applied, ie the complexity of sorting dominates the algorithm. This is O ( | E | log | V | ).

• Graph search algorithm
• Optimization algorithm