_Anim.gif) Animation of Borůvka's algorithm | |
| Class | Minimum spanning tree algorithm |
|---|---|
| Data structure | Graph |
| Worst-caseperformance | |
Borůvka's algorithm is agreedy algorithm for finding aminimum 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 byOtakar Borůvka as a method of constructing an efficientelectricity network forMoravia.[1][2][3]The algorithm was rediscovered byChoquet in 1938;[4] again byFlorek,Łukasiewicz,Perkal,Steinhaus, andZubrzycki in 1951;[5] and again by Georges Sollin in 1965.[6] This algorithm is frequently calledSollin's algorithm, especially in theparallel 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.
The following pseudocode illustrates a basic implementation of Borůvka's algorithm.In the conditional clauses, every edgeuv is considered cheaper than "None". The purpose of thecompleted variable is to determine whether the forestF is yet a spanning forest.
If edges do not have distinct weights, then a consistenttie-breaking rule must be used, e.g. based on sometotal order on vertices or edges.This can be achieved by representing vertices as integers and comparing them directly; comparing theirmemory addresses; etc.A tie-breaking rule is necessary to ensure that the created graph is indeed a forest, that is, it does not contain cycles. For example, consider a triangle graph with nodes {a,b,c} and all edges of weight 1. Then a cycle could be created if we selectab as the minimal weight edge for {a},bc for {b}, andca for {c}.A tie-breaking rule which orders edges first by source, then by destination, will prevent creation of a cycle, resulting in the minimal spanning tree {ab,bc}.
algorithm Borůvkaisinput: A weighted undirected graphG = (V,E).output:F, a minimum spanning forest ofG. Initialize a forestF to (V,E′) whereE′ = {}.completed :=falsewhile notcompleteddo Find theconnected components ofF and assign to each vertex its component Initialize the cheapest edge for each component to "None"for each edgeuv inE, whereu andv are in different components ofF: letwx be the cheapest edge for the component ofuif is-preferred-over(uv,wx)then Setuv as the cheapest edge for the component ofu letyz be the cheapest edge for the component ofvif is-preferred-over(uv,yz)then Setuv as the cheapest edge for the component ofvif all components have cheapest edge set to "None"then// no more trees can be merged -- we are finishedcompleted :=trueelsecompleted :=falsefor each component whose cheapest edge is not "None"do Add its cheapest edge toE'function is-preferred-over(edge1,edge2)isreturn (edge2 is "None") or (weight(edge1) < weight(edge2)) or (weight(edge1) = weight(edge2) and tie-breaking-rule(edge1,edge2))function tie-breaking-rule(edge1,edge2)is The tie-breaking rule; returnstrue if and only ifedge1 is preferred overedge2 in the case of a tie.
As an optimization, one could remove fromG each edge that is found to connect two vertices in the same component, so that it does not contribute to the time for searching for cheapest edges in later components.
Borůvka's algorithm can be shown to takeO(logV) iterations of the outer loop until it terminates, and therefore to run in timeO(E logV), whereE is the number of edges, andV is the number of vertices inG (assumingE ≥V). Inplanar graphs, and more generally in families of graphs closed undergraph 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]
| 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 for this problem includePrim's algorithm andKruskal'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 expectedO(E) time.[9] The best known (deterministic) minimum spanning tree algorithm byBernard Chazelle is also based in part on Borůvka's and runs inO(E α(E,V)) time, where α is theinverse 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.