Borůvka's algorithm: Difference between revisions

Revision as of 00:47, 18 June 2021

Latest revision as of 14:54, 27 March 2025

(18 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

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

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

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 53 ⟶ 60:

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

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

''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'''let ''uvwx'' is cheaper thanbe the cheapest edge for the component of ''u'' '''then'''

'''if''' is-preferred-over(''uv'', ''wx'') '''then'''

Set ''uv'' as the cheapest edge for the component of ''u''

'''if'''let ''uvyz'' is cheaper thanbe the cheapest edge for the component of ''v'' '''then'''

'''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.

Line 76 ⟶ 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 100 ⟶ 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 the inverse of the [[Ackermann function#Inverse|inverse 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]]