Borůvka's algorithm
_Anim.gif?lang=en)
Template:Graph search algorithm
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected.
It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.[1][2][3] The algorithm was rediscovered by Choquet in 1938;[4] again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951;[5] and again by Georges Sollin in 1965.[6] This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.
The algorithm begins by finding the minimum-weight edge incident to each vertex of the graph, and adding all of those edges to the forest. Then, it repeats a similar process of finding the minimum-weight edge from each tree constructed so far to a different tree, and adding all of those edges to the forest. Each repetition of this process reduces the number of trees, within each connected component of the graph, to at most half of this former value, so after logarithmically many repetitions the process finishes. When it does, the set of edges it has added forms the minimum spanning forest.
Pseudocode
algorithm Borůvka is
input: A weighted undirected graph G = (V, E).
output: F, the minimum spanning forest of G.
Initialize a forest F to (V, E').
completed = false
while not completed do
Find the connected components of F and assign to each vertex its component
Initialize the cheapest edge for each component to "None"
for each edge uv where u and v are in different components:
if uv is cheaper than the cheapest edge for the component of u then
Set uv as the cheapest edge for the component of u
if uv is cheaper than the cheapest edge for the component of v then
Set uv as the cheapest edge for the component of v
if all components have cheapest edge set to "None" then
// no more trees can be merged -- we are finished
completed = true
else
completed = false
for each component whose cheapest edge is not "None" do
Add its cheapest edge to E'
In the conditional clauses, every edge uv is considered cheaper than "None". The purpose of the completed variable is to determine whether the forest F is yet a spanning forest. If edges do not have distinct weights, then a consistent tie-breaking rule can be used (e.g. based on some total order on vertices or edges).
As an optimization, we could remove from G each edge that is found to connect two vertices in the same component. An even more important optimization would be to keep track of which vertex belongs to which component, and update this information when an edge is added to E', instead of recomputing this information in each iteration of the while loop.
Complexity
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(E log 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.[7]
Example
| Image | components | Description |
|---|---|---|
|
{A} {B} {C} {D} {E} {F} {G} |
This is our original weighted graph. The numbers near the edges indicate their weight. Initially, every vertex by itself is a component (blue circles). |
|
{A,B,D,F} {C,E,G} |
In the first iteration of the outer loop, the minimum weight edge out of every component is added. Some edges are selected twice (AD, CE). Two components remain. |
|
{A,B,C,D,E,F,G} | In the second and final iteration, the minimum weight edge out of each of the two remaining components is added. These happen to be the same edge. One component remains and we are done. The edge BD is not considered because both endpoints are in the same component. |
Other algorithms
Other algorithms for this problem include Prim's algorithm and Kruskal's algorithm. Fast parallel algorithms can be obtained by combining Prim's algorithm with Borůvka's.[8]
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.[9] 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 α(E,V)) time, where α is the inverse of the Ackermann function.[10] 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.
Notes
- ^ Borůvka, Otakar (1926). "O jistém problému minimálním" [About a certain minimal problem]. Práce Mor. Přírodověd. Spol. V Brně III (in Czech and German). 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)". Elektronický Obzor (in Czech). 15: 153–154.
- ^ Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history". Discrete Mathematics. 233 (1–3): 3–36. doi:10.1016/S0012-365X(00)00224-7. hdl:10338.dmlcz/500413. MR 1825599.
- ^ Choquet, Gustave (1938). "Étude de certains réseaux de routes". Comptes Rendus de l'Académie des Sciences (in French). 206: 310–313.
- ^ Florek, K.; Łukaszewicz, J.; Perkal, J.; Steinhaus, Hugo; Zubrzycki, S. (1951). "Sur la liaison et la division des points d'un ensemble fini". Colloquium Mathematicae (in French). 2: 282–285. MR 0048832.
- ^ Sollin, Georges (1965). "Le tracé de canalisation". Programming, Games, and Transportation Networks (in French).
- ^ Eppstein, David (1999). "Spanning trees and spanners". In Sack, J.-R.; Urrutia, J. (eds.). Handbook of Computational Geometry. Elsevier. pp. 425–461.; Mareš, Martin (2004). "Two linear time algorithms for MST on minor closed graph classes" (PDF). Archivum Mathematicum. 40 (3): 315–320..
- ^ Bader, David A.; Cong, Guojing (2006). "Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs". Journal of Parallel and Distributed Computing. 66 (11): 1366–1378. CiteSeerX 10.1.1.129.8991. doi:10.1016/j.jpdc.2006.06.001.
- ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM. 42 (2): 321–328. CiteSeerX 10.1.1.39.9012. doi:10.1145/201019.201022.
- ^ Chazelle, Bernard (2000). "A minimum spanning tree algorithm with inverse-Ackermann type complexity" (PDF). J. ACM. 47 (6): 1028–1047. CiteSeerX 10.1.1.115.2318. doi:10.1145/355541.355562.