Boruvka'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 efficiently electrifying Bohemia.

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

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

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

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 algorithm due to Karger, Klein and Tarjan runs in expected <math>O(E)<math> time.