Content deleted Content added
or actually I think Georges |
m RCP reverted edits by 186.185.247.155 (Talk); changed back to last revision by JJMC89 bot III: Unconstructive edit |
||
(47 intermediate revisions by 23 users not shown) | |||
Line 1:
{{Short description|Method for finding minimum spanning trees}}
[[File:Boruvka's algorithm (Sollin's algorithm) Anim.gif|thumb|upright=1.35|Animation of Boruvka's algorithm]]▼
{{Infobox Algorithm
▲|image=[[File:Boruvka's algorithm (Sollin's algorithm) Anim.gif|
|caption=Animation of Borůvka's algorithm
'''Borůvka's algorithm''' is an [[algorithm]] for finding a [[minimum spanning tree]] in a graph for which all edge weights are distinct,▼
|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
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 |
| last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
| last2 = Milková | first2 = Eva
Line 16 ⟶ 21:
| title = Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history
| volume = 233
| year = 2001
| hdl-access = free
The algorithm was rediscovered by [[Gustave Choquet|Choquet]] in 1938;<ref>{{cite journal | last = Choquet | first = Gustave | authorlink = 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–313 | language = French }}</ref> again by [[Kazimierz Florek|Florek]], [[Jan Łukasiewicz|Łukasiewicz]], [[Julian Perkal|Perkal]], [[Hugo Steinhaus|Steinhaus]], and [[Stefan Zubrzycki|Zubrzycki]] in 1951;<ref>{{cite journal▼
}}</ref>
▲The algorithm was rediscovered by [[Gustave Choquet|Choquet]] in 1938;<ref>{{cite journal | last = Choquet | first = Gustave |
| last1 = Florek | first1 = K.
| last2 = Łukaszewicz | first2 = J. | author2-link = Jan Łukasiewicz
Line 23 ⟶ 30:
| last4 = Steinhaus | first4 = Hugo | author4-link = Hugo Steinhaus
| last5 = Zubrzycki | first5 = S.
| journal = Colloquium
| language =
| mr = 0048832
| pages = 282–285
Line 30 ⟶ 37:
| url = https://eudml.org/doc/209969
| volume = 2
| year = 1951| issue = 3–4
| year = 1951}}</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 = French }}</ref> This algorithm is frequently called '''Sollin's algorithm''', especially in the [[parallel computing]] literature.▼
| doi = 10.4064/cm-2-3-4-282-285
▲
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.
Line 38 ⟶ 47:
== Pseudocode ==
Find the connected components of ''F'' and label each vertex of ''G'' by its component▼
Initialize the cheapest edge for each component to "None"▼
If ''uv'' is cheaper than the cheapest edge for the component of ''u'':▼
Set ''uv'' as the cheapest edge for the component of ''u''▼
If ''uv'' is cheaper than the cheapest edge for the component of ''v'':▼
Set ''uv'' as the cheapest edge for the component of ''v''▼
For each component whose cheapest edge is not "None":▼
Add its cheapest edge to ''F''▼
Output: ''F'' is the minimum spanning forest of ''G''.▼
The following pseudocode illustrates a basic implementation of Borůvka's algorithm.
If edges do not have distinct weights, then a consistent tie-breaking rule (e.g. breaking ties by the object identifiers of the edges) can be used.▼
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.
An optimization (not necessary for the analysis) is to remove from ''G'' each edge that is found to connect two vertices in the same component as each other.▼
▲If edges do not have distinct weights, then a consistent '''tie-breaking rule''' must be used,
This can be achieved by representing vertices as integers and comparing them directly; comparing their [[memory address]]es; 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''}.
'''algorithm''' Borůvka '''is'''
'''input:''' A weighted undirected graph ''G'' = (''V'', ''E'').
Initialize a forest ''F'' to (''V'', ''{{prime|E}}'') where ''{{prime|E}}'' = {}.
''completed'' := '''false'''
'''while''' not ''completed'' '''do'''
▲ Find the [[Component_(graph_theory)|connected
▲ Initialize the cheapest edge for each component to "None"
'''for each''' edge ''uv'' in ''E'', where ''u'' and ''v'' are in different components of ''F'':
'''if''' is-preferred-over(''uv'', ''wx'') '''then'''
▲ Set ''uv'' as the cheapest edge for the component of ''u''
'''if''' is-preferred-over(''uv'', ''yz'') '''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'''
'''function''' is-preferred-over(''edge1'', ''edge2'') '''is'''
'''return''' (''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; returns '''true''' if and only if ''edge1''
is preferred over ''edge2'' in the case of a tie.
▲
== Complexity ==
Borůvka's algorithm can be shown to take {{math|[[Big O notation|O]](log ''V'')}} iterations of the outer loop until it terminates, and therefore to run in time {{math|[[Big O notation|O]](''E'' log ''V'')}}, where
== Example ==
{|
! | Image
! width="100" | components
Line 83 ⟶ 118:
== 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.<ref>{{cite journal|last1=Bader|first1=David A.|last2=Cong|first2=Guojing|title=Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs|journal=Journal of Parallel and Distributed Computing|date=2006|volume=66|issue=11|pages=1366–1378|doi=10.1016/j.jpdc.2006.06.001|citeseerx=10.1.1.129.8991|s2cid=2004627}}</ref>
A faster randomized minimum spanning tree algorithm based in part on Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected {{math|O(''E'')}} time.<ref>{{cite journal|last1=Karger|first1=David R.|last2=Klein|first2=Philip N.|last3=Tarjan|first3=Robert E.|title=A randomized linear-time algorithm to find minimum spanning trees|journal=Journal of the ACM|date=1995|volume=42|issue=2|pages=321–328|doi=10.1145/201019.201022|citeseerx=10.1.1.39.9012|s2cid=832583}}</ref> The best known (deterministic) minimum spanning tree algorithm by [[Bernard Chazelle]] is also based in part on Borůvka's and runs in {{math|O(''E'' α(''E'',''V''))}} time, where α is
==Notes==
<references/>
{{Graph traversal algorithms}}
[[Category:Graph algorithms]]
[[Category:Spanning tree]]
|