Borůvka's algorithm

From Wikipedia, the free encyclopedia

Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct.

It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Bohemia.^[1][2] The algorithm was rediscovered by Choquet in 1938; ^[3] again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Sollin some time in the early 1960s. Because Sollin was the only Western computer scientist in this list, this algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.

The algorithm begins by examining each vertex and adding the cheapest edge from that vertex to another in the graph, without regard to already added edges, and continues joining these groupings in a like manner until a tree spanning all vertices is completed. Designating each vertex or set of connected vertices a "component", pseudocode for Borůvka's algorithm is:

• Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T
• While the vertices of G connected by T are disjoint:
  • Begin with an empty set of edges E
  • For each component:
    • Begin with an empty set of edges S
    • For each vertex in the component:
      • Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S
    • Add the cheapest edge in S to E
  • Add the resulting set of edges E to T.
• The resulting set of edges T is the minimum spanning tree of G

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 (actually discovered by Vojtěch Jarník) 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 O(E) time. The best known (deterministic) 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.

[edit] References

1. ^ Borůvka, Otakar (1926). "O jistém problému minimálním (About a certain minimal problem)" (in Czech, German summary). Práce mor. přírodověd. spol. v Brně III 3: 37–58. 
2. ^ Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)" (in Czech). Elektronický Obzor 15: 153–154. 
3. ^ Choquet, Gustave (1938). "Étude de certains réseaux de routes" (in French). Comptes-rendus de l’Académie des Sciences 206: 310–313.