Editing Borůvka's algorithm (section)

{{Short description|Method for finding minimum spanning trees}}
{{Infobox Algorithm
|image=[[File:Boruvka's algorithm (Sollin's algorithm) Anim.gif|frameless|upright=1.35]]
|caption=Animation of Borůvka's algorithm
|class=[[Minimum spanning tree|Minimum spanning tree algorithm]]
|data=[[Graph (abstract data type)|Graph]]
|time=<math>O(|E|\log |V|)</math>
}}
'''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]].<ref>{{cite journal | last = Borůvka | first = Otakar | author-link = Otakar Borůvka | year = 1926 | title = O jistém problému minimálním |trans-title=About a certain minimal problem | journal = Práce Mor. Přírodověd. Spol. V Brně III | volume = 3 | pages = 37–58 | url = https://dml.cz/handle/10338.dmlcz/500114 | language = cs, de}}</ref><ref>{{cite journal | last = Borůvka | first = Otakar | author-link = Otakar Borůvka | year = 1926 | title = 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) | journal = Elektronický Obzor | volume = 15 | pages = 153&ndash;154 | language = cs }}</ref><ref>{{cite journal
 | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
 | last2 = Milková | first2 = Eva
 | last3 = Nešetřilová | first3 = Helena
 | doi = 10.1016/S0012-365X(00)00224-7
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1825599
 | pages = 3–36
 | title = Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history
 | volume = 233
 | year = 2001| hdl = 10338.dmlcz/500413
 | hdl-access = free
 }}</ref>
The algorithm was rediscovered by [[Gustave Choquet|Choquet]] in 1938;<ref>{{cite journal | last = Choquet | first = Gustave | author-link = Gustave Choquet | year = 1938 | title = Étude de certains réseaux de routes | journal = Comptes Rendus de l'Académie des Sciences | volume = 206 | pages = 310&ndash;313 | language = fr }}</ref> again by [[Kazimierz Florek|Florek]],  [[Jan Łukasiewicz|Łukasiewicz]], [[Julian Perkal|Perkal]], [[Hugo Steinhaus|Steinhaus]], and [[Stefan Zubrzycki|Zubrzycki]] in 1951;<ref>{{cite journal
 | last1 = Florek | first1 = K.
 | last2 = Łukaszewicz | first2 = J. | author2-link = Jan Łukasiewicz
 | last3 = Perkal | first3 = J.
 | last4 = Steinhaus | first4 = Hugo | author4-link = Hugo Steinhaus
 | last5 = Zubrzycki | first5 = S.
 | journal = Colloquium Mathematicum
 | language = fr
 | mr = 0048832
 | pages = 282–285
 | title = Sur la liaison et la division des points d'un ensemble fini
 | url = https://eudml.org/doc/209969
 | volume = 2
 | year = 1951| issue = 3–4
 | doi = 10.4064/cm-2-3-4-282-285
 }}</ref> and again by Georges Sollin in 1965.<ref>{{cite journal | last = Sollin | first = Georges | year = 1965 | title = Le tracé de canalisation | journal = Programming, Games, and Transportation Networks |  language = fr }}</ref> 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.