Content deleted Content added
→Pseudocode: specify that E' is initially empty |
m RCP reverted edits by 186.185.247.155 (Talk); changed back to last revision by JJMC89 bot III: Unconstructive edit |
||
(27 intermediate revisions by 13 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
|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.
Line 25 ⟶ 30:
| last4 = Steinhaus | first4 = Hugo | author4-link = Hugo Steinhaus
| last5 = Zubrzycki | first5 = S.
| journal = Colloquium
| language = fr
| mr = 0048832
Line 32 ⟶ 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 = fr }}</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 40 ⟶ 47:
== 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'''
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'').
'''output:''' ''F'',
Initialize a forest ''F'' to (''V'', ''{{prime|E
''completed'' := '''false'''
'''while''' not ''completed'' '''do'''
Find the [[Component_(graph_theory)|connected component]]s of ''F'' and assign to each vertex its component
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'''
'''for each''' component whose cheapest edge is not "None" '''do'''
Add its cheapest edge to ''E'''
'''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.
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.
▲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 can be used (e.g. based on some [[total order]] on vertices or edges).
== 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 ==
Line 93 ⟶ 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]]
|