Borůvka's algorithm

It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia. The algorithm was rediscovered by Choquet in 1938; again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Georges Sollin in 1965. 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

The following pseudocode illustrates a basic implementation of Borůvka's algorithm. 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 must be used, e.g. based on some total order on vertices or edges. This can be achieved by representing vertices as integers and comparing them directly; comparing their memory 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 select ab as the minimal weight edge for {a}, bc for {b}, and ca 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}.

<b id="mwRA">algorithm</b> Borůvka <b id="mwRQ">is</b> <b id="mwRg">input:</b> A weighted undirected graph <i id="mwRw">G</i> = (<i id="mwSA">V</i>, <i id="mwSQ">E</i>). <b id="mwSg">output:</b> <i id="mwSw">F</i>, a minimum spanning forest of <i id="mwTA">G</i>. Initialize a forest <i id="mwTQ">F</i> to (<i id="mwTg">V</i>, <i id="mwTw"><span about="#mwt23" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"prime","href":"./Template:Prime"},"params":{"1":{"wt":"E"}},"i":0}}]}' id="mwUA">E</span><span class="nowrap" style="padding-left:0.05em;" about="#mwt23" id="mwUQ">′</span></i>) where <i id="mwUg"><span about="#mwt24" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"prime","href":"./Template:Prime"},"params":{"1":{"wt":"E"}},"i":0}}]}' id="mwUw">E</span><span class="nowrap" style="padding-left:0.05em;" about="#mwt24" id="mwVA">′</span></i> = {}. <i id="mwVQ">completed</i> := <b id="mwVg">false</b> <b id="mwVw">while</b> not <i id="mwWA">completed</i> <b id="mwWQ">do</b> Find the <a rel="mw:WikiLink" href="./Component_(graph_theory)" title="Component (graph theory)" id="mwWg">connected components</a> of <i id="mwWw">F</i> and assign to each vertex its component Initialize the cheapest edge for each component to "None" <b id="mwXA">for each</b> edge <i id="mwXQ">uv</i> in <i id="mwXg">E</i>, where <i id="mwXw">u</i> and <i id="mwYA">v</i> are in different components of <i id="mwYQ">F</i>: let <i id="mwYg">wx</i> be the cheapest edge for the component of <i id="mwYw">u</i> <b id="mwZA">if</b> is-preferred-over(<i id="mwZQ">uv</i>, <i id="mwZg">wx</i>) <b id="mwZw">then</b> Set <i id="mwaA">uv</i> as the cheapest edge for the component of <i id="mwaQ">u</i> let <i id="mwag">yz</i> be the cheapest edge for the component of <i id="mwaw">v</i> <b id="mwbA">if</b> is-preferred-over(<i id="mwbQ">uv</i>, <i id="mwbg">yz</i>) <b id="mwbw">then</b> Set <i id="mwcA">uv</i> as the cheapest edge for the component of <i id="mwcQ">v</i> <b id="mwcg">if</b> all components have cheapest edge set to "None" <b id="mwcw">then</b> <i id="mwdA">// no more trees can be merged -- we are finished</i> <i id="mwdQ">completed</i> := <b id="mwdg">true</b> <b id="mwdw">else</b> <i id="mweA">completed</i> := <b id="mweQ">false</b> <b id="mweg">for each</b> component whose cheapest edge is not "None" <b id="mwew">do</b> Add its cheapest edge to <i id="mwfA">E'</i> <b id="mwfQ">function</b> is-preferred-over(<i id="mwfg">edge1</i>, <i id="mwfw">edge2</i>) <b id="mwgA">is</b> <b id="mwgQ">return</b> (<i id="mwgg">edge2</i> is "None") or (weight(<i id="mwgw">edge1</i>) < weight(<i id="mwhA">edge2</i>)) or (weight(<i id="mwhQ">edge1</i>) = weight(<i id="mwhg">edge2</i>) and tie-breaking-rule(<i id="mwhw">edge1</i>, <i id="mwiA">edge2</i>)) <b id="mwiQ">function</b> tie-breaking-rule(<i id="mwig">edge1</i>, <i id="mwiw">edge2</i>) <b id="mwjA">is</b> The tie-breaking rule; returns <b id="mwjQ">true</b> if and only if <i id="mwjg">edge1</i> is preferred over <i id="mwjw">edge2</i> in the case of a tie.

As an optimization, one could remove from G 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.