Borůvka's algorithm: Difference between revisions

Revision as of 10:19, 1 April 2006

Revision as of 20:03, 7 May 2006

Line 1:

'''Borůvka's algorithm''' is an [[algorithm]] for finding a [[minimum spanning tree]] 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 [[K._Florek|Florek]], [[Jan Łukasiewicz|LukasiewiczŁukasiewicz]], [[Perkal]], [[StienhausHugo Steinhaus|Steinhaus]], and [[Stefan Zubrzycki|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 continues joining these groupings 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: