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 Moravia.

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

• Copy the vertices of G into a new graph, L, with no edges.
• While L is not connected (that is, it is a forest of more than one tree):
  • For each tree T in L, find the smallest edge in G connecting a vertex in T to one outside it.
  • Add that edge to L, reducing the number of trees in L by one.

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 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.