Borůvka's algorithm: Difference between revisions

Revision as of 07:11, 14 November 2021

Latest revision as of 14:54, 27 March 2025

(16 intermediate revisions by 11 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

{{graph search algorithm}}

|image=[[File:Boruvka's algorithm (Sollin's algorithm) Anim.gif|thumbframeless|upright=1.35|Animation of Boruvka's algorithm]]

|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 MathematicaeMathematicum

| language = fr

| mr = 0048832

Line 55 ⟶ 60:

'''output:''' ''F'', a minimum spanning forest of ''G''.

Initialize a forest ''F'' to (''V'', ''{{prime|E&apos;}}'') where ''{{prime|E&apos;}}'' = {}.

''completed'' := '''false'''

Line 77 ⟶ 82:

'''function''' is-preferred-over(''edge1'', ''edge2'') '''is'''

'''return''' (''edge1edge2'' is "None") or

(weight(''edge1'') < weight(''edge2'')) or

(weight(''edge1'') = weight(''edge2'') and tie-breaking-rule(''edge1'', ''edge2''))

Line 89 ⟶ 94:

== 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 ''{{mvar|E''}} is the number of edges, and ''{{mvar|V''}} is the number of vertices in ''{{mvar|G''}} (assuming {{math|''E'' ≥ ''V''}}). In [[planar graph]]s, and more generally in families of graphs closed under [[graph minor]] operations, it can be made to run in linear time, by removing all but the cheapest edge between each pair of components after each stage of the algorithm.<ref>{{Cite book|last=Eppstein|first=David|author-link=David Eppstein|contribution=Spanning trees and spanners|title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor1-link=Jörg-Rüdiger Sack|editor2-first=J.|editor2-last=Urrutia|editor2-link= Jorge Urrutia Galicia|publisher=Elsevier|year=1999|pages=425–461}}; {{Cite journal|last=Mareš|first=Martin|title=Two linear time algorithms for MST on minor closed graph classes|journal=Archivum Mathematicum|volume=40|year=2004|issue=3|pages=315–320|url=http://www.emis.de/journals/AM/04-3/am1139.pdf}}.</ref>

== Example ==

Line 115 ⟶ 120:

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 the [[Ackermann function#Inverse|inverse of the [[Ackermann function]].<ref>{{Cite journal|last=Chazelle|first=Bernard|title=A minimum spanning tree algorithm with inverse-Ackermann type complexity|journal=J. ACM|volume=47|year=2000|issue=6|pages=1028–1047|url=http://www.cs.princeton.edu/~chazelle/pubs/mst.pdf|doi=10.1145/355541.355562|citeseerx=10.1.1.115.2318|s2cid=6276962}}</ref> These randomized and deterministic algorithms combine steps of Borůvka's algorithm, reducing the number of components that remain to be connected, with steps of a different type that reduce the number of edges between pairs of components.

==Notes==

<references/>

{{Graph traversal algorithms}}

{{DEFAULTSORT:Boruvka's Algorithm}}

[[Category:Graph algorithms]]

[[Category:Spanning tree]]