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 constructing an efficient electricity network for Bohemia.
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 <math>O(E)<math> 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.