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 Moravia.[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 take O(log V) iterations of the outer loop until it terminates, and therefore to run in time O(Elog V), where E is the number of edges, and V is the number of vertices in G. In planar graphs, and more generally in families of graphs closed under graph minor operations, it can be made to run in linear time, by removing all but the cheapest edge between each pair of components after each stage of the algorithm.[4]
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 minimum spanning tree algorithm based in part on 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 also based in part on Borůvka's and runs in O(E α(V)) time, where α is the inverse of the Ackermann function. These randomized and deterministic algorithms combine steps of Borůvka's algorithm, reducing the number of components that remain to be connected, with steps of a different type that reduce the number of edges between pairs of components.
[edit] References
- ^ 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.
- ^ 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.
- ^ Choquet, Gustave (1938). "Étude de certains réseaux de routes" (in French). Comptes-rendus de l’Académie des Sciences 206: 310–313.
- ^ Eppstein, David (1999), “Spanning trees and spanners”, in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry, Elsevier, pp. 425–461; Mareš, Martin (2004), “Two linear time algorithms for MST on minor closed graph classes”, Archivum mathematicum 40 (3): 315–320, <http://www.emis.de/journals/AM/04-3/am1139.pdf>.
