Borůvka's algorithm: Difference between revisions

Revision as of 07:56, 11 September 2005

Revision as of 03:49, 15 November 2005

Line 1:

'''Borůvka's algorithm''' is an [[algorithm]] for finding [[minimum spanning tree]]s. It was first published in [[1926]] by [[Otakar Borůvka]] as a method of constructing an efficient electricity network for [[Moravia]]. The algorithm was rediscovered by [[Choquet]] in 1938; again by [[Florek]], [[Lukaziewicz]], [[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.

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

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

*While ''L''the isgraph not connected (that is, it is a forest ofhas more than one tree):component

**ForFind eachthe treesafe ''T''edges infor ''L'',each findcomponent the(a smallestsafe edge inis ''G''an connectingedge awith exactly one vertex in ''T'' to one outsidethe it.component)

**Add thatall edgeof tothese ''L'',edges reducing the number of trees into ''L'' by one.

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

Other algorithms for this problem include [[Prim's algorithm]] (actually discovered by [[Vojtech Jarnik]]) and [[Kruskal's algorithm]]. Faster algorithms can be obtained by combining Prim's algorithm with Bor&#367;vka's. A faster randomized version of Bor&#367;vka's algorithm due to Karger, Klein, and Tarjan runs in expected <math>O(E)</math> time. The best known minimum spanning tree algorithm by [[Bernard Chazelle]] is based on Bor&#367;vka's and runs in O(''E'' &alpha;(V)) time, where &alpha; is the inverse of the [[Ackermann function]].

[[Category:Trees (structure)]]

[[Category:Graph algorithms]]