Borůvka's algorithm: Difference between revisions

Revision as of 03:44, 8 March 2006

Revision as of 10:18, 1 April 2006

Line 1:

'''Borůvka's algorithm''' is an [[algorithm]] for finding a [[minimum spanning tree]]s. in a graph for which all edge weights are distinct.

It was first published in [[1926]] by [[Otakar Borůvka]] as a method of constructing an efficient electricity network for [[Bohemia]]. The algorithm was rediscovered by [[Choquet]] in 1938; again by [[Florek]], [[Jan Łukasiewicz|Lukasiewicz]], [[Perkal]], [[Stienhaus]], and [[Zubrzycki]] in 1951; and again by [[Sollin]] some time in the early 1960s. Because [[Sollin]] was the only Western computer scientist in this list—[[Choquet]] was a civil engineer; [[Florek]] and his co-authors were anthropologists—this algorithm is frequently but incorrectly called ‘[[Sollin]]’s algorithm’, especially in the parallel computing literature.

The algorithm begins by examining each vertex and adding the cheapest edge from that vertex to another in the graph, without regard to already added edges, and contines joining these grouping in a like manner until a tree spanning all vertices is completed. Designating each vertex or set of connected vertices a "component", pseudocode for Borůvka's algorithm is:

Borůvka's algorithm, in pseudocode, given a connected graph ''G'', is:

*Begin with a connected graph ''G'' containing edges of distinct weights, and an empty set of edges ''T''

*CopyWhile the vertices of ''G'' intoconnected a new graph,by ''LT'', with noare edges.disjoint:

**Begin with an empty set of edges ''E''

**For each component:

***Begin with an empty set of edges ''S''

***For each vertex in the component:

****Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to ''S''

***Add the cheapest edge in ''S'' to ''E''

**Add allthe ofresulting theseset of edges ''E'' to ''LT''.

*The resulting set of edges ''T'' is minimum spanning tree of ''G''

*Copy the vertices of ''G'' into a new graph, ''L'', with no edges.

*While the graph has more than one component

**For each component, find the cheapest edge with exactly one vertex in the component

**Add all of these edges to ''L''.

Borůvka's algorithm can be shown to run in time [[Big O notation|O]](''E''log ''V''), where ''E'' is the number of edges, and ''V'' is the number of vertices in ''G''.

Line 17 ⟶ 24:

[[Category:Graph algorithms]]

[[Category:Polynomial-time problems]]

{{compu-sci-stub}}