Borůvka's algorithm

Borůvka's algorithm is an algorithm for finding minimum spanning trees.

It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Bohemia. The algorithm was rediscovered by Choquet in 1938; again by Florek, Lukaziewicz, Perkal, Stienhaus, and Zubrzycki in 1951; and again by Sollin some time in the early 1960s. Because Sollin was the only Western computer scientist in this list—Choquet was a civil engineer; Florek and his co-authors were anthropologists—this algorithm is frequently but incorrectly called ‘Sollin’s algorithm’, especially in the parallel computing literature.

Borůvka's algorithm, in pseudocode, given a connected graph G, is:

• Copy the vertices of G into a new graph, L, with no edges.
• While the graph has more than one component
  • For each component, find the cheapest edge with exactly one vertex in the component
  • Add all of these edges to L.

Borůvka's algorithm can be shown to run in time O(Elog V), where E is the number of edges, and V is the number of vertices in G.

Other algorithms for this problem include Prim's algorithm (actually discovered by Vojtech Jarnik) and Kruskal's algorithm. Faster algorithms can be obtained by combining Prim's algorithm with Borůvka's. A faster randomized version of Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected ${\displaystyle O(E)}$ time. The best known minimum spanning tree algorithm by Bernard Chazelle is based on Borůvka's and runs in O(E α(V)) time, where α is the inverse of the Ackermann function.