Borwka Algorithm

Boruvki Algorithm ( Boruvka-Sullin Algorithm ) is an algorithm for finding the minimum spanning tree in a graph.

It was first published in 1926 by as a method of finding the optimal electrical network in Moravia . It was rediscovered several times, for example by Florek , Perkal and Sullin . The latter, in addition, was the only Western scientist from this list, and therefore the algorithm is often called the Sullin algorithm , especially in the literature on parallel computing .

Content

1 Algorithm
- 1.1 Algorithm Complexity
2 See also
3 Literature
4 notes

Algorithm

The operation of the algorithm consists of several iterations, each of which consists of sequentially adding edges to the spanning forest of the graph until the forest turns into a tree , that is, a forest consisting of one connected component.

In pseudo-code, the algorithm can be described as follows:

Initially let $T$ ${\ displaystyle T}$ - an empty set of edges (representing a spanning forest, into which each peak enters as a separate tree).
Until $T$ {\ displaystyle T} is not a tree (which is equivalent to the condition: while the number of edges in $T$ {\ displaystyle T} less than $V$ $-$ $one$ {\ displaystyle V-1} where $V$ {\ displaystyle V} - the number of vertices in the graph):
- For each connected component (that is, a tree in a spanning forest) in a subgraph with edges $T$ ${\ displaystyle T}$ , we find the cheapest edge connecting this component with some other connected component. (It is assumed that the weights of the edges are different, or somehow additionally ordered so that you can always find a single edge with a minimum weight).
- Add all the edges found to the set. $T$ ${\ displaystyle T}$ .
The resulting set of edges $T$ ${\ displaystyle T}$ is a minimal spanning tree of the input graph.

Algorithm Complexity

At each iteration, the number of trees in the spanning forest is reduced by at least two times, therefore, the algorithm performs no more than $O(\log V)$ ${\ displaystyle O (\ log V)}$ iterations. Each iteration can be implemented with complexity. $O(E)$ ${\ displaystyle O (E)}$ , so the total runtime of the algorithms is $O(E\log V)$ ${\ displaystyle O (E \ log V)}$ time (here $V$ ${\ displaystyle V}$ and $E$ ${\ displaystyle E}$ - the number of vertices and edges in the graph, respectively).

However, for some types of graphs, in particular planar ones , it can be reduced to $O(E)$ ${\ displaystyle O (E)}$ . ^[1] There is also a randomized algorithm for constructing a minimum spanning tree based on the Boruwka algorithm, working on average in linear time.

Literature

Sedgwick R. Fundamental algorithms in C ++, part 5. Algorithms on graphs. ISBN 5-93772-082-2 .

Notes

↑ Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry , Elsevier, p. 425-461 ; Mareš, Martin (2004), " Two linear time algorithms for MST on minor closed graph classes ", Archivum mathematicum T. 40 (3): 315–320 , < http://www.emis.de/journals/AM/04 -3 / am1139.pdf > .

[1] Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry , Elsevier, p. 425-461 ; Mareš, Martin (2004), " Two linear time algorithms for MST on minor closed graph classes ", Archivum mathematicum T. 40 (3): 315–320 , < http://www.emis.de/journals/AM/04 -3 / am1139.pdf > .