Borůvka's algorithm: Difference between revisions

Revision as of 23:31, 27 February 2023

Latest revision as of 14:54, 27 March 2025

(8 intermediate revisions by 6 users not shown)

Line 2:

{{Infobox Algorithm

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

|caption=Animation of BoruvkaBorůvka's algorithm

|class=[[Minimum spanning tree|Minimum spanning tree algorithm]]

|data=[[Graph (abstract data type)|Graph]]

Line 30:

| last4 = Steinhaus | first4 = Hugo | author4-link = Hugo Steinhaus

| last5 = Zubrzycki | first5 = S.

| journal = Colloquium MathematicaeMathematicum

| language = fr

| mr = 0048832

Line 60:

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

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

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

Line 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==

Line 127:

{{Graph traversal algorithms}}

{{DEFAULTSORT:Boruvka's Algorithm}}

[[Category:Graph algorithms]]

[[Category:Spanning tree]]