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

Borůvka's algorithm, in pseudocode, given a graph ${\displaystyle G}$, is:

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

Borůvka's algorithm can be shown to run in time O(${\displaystyle E}$ log ${\displaystyle V}$), where ${\displaystyle E}$ is the number of edges, and ${\displaystyle V}$ is the number of vertices in ${\displaystyle 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 algorithm due to Karger, Klein and Tarjan runs in expected ${\displaystyle O(E)}$ time.