Borůvka's algorithm: Difference between revisions

Revision as of 18:17, 19 April 2022

Revision as of 19:40, 27 February 2023

Line 1:

{{Short description|Method for finding minimum spanning trees}}

{{Infobox Algorithm

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

|caption=Animation of Boruvka'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 88 ⟶ 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 ==