The Boruvka's algorithm reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

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 , is:

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

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

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

This is the "Boruvka's algorithm" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.