Borůvka's algorithm: Difference between revisions

Revision as of 22:15, 7 May 2006

Revision as of 10:24, 12 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&#367;vka]] as a method of constructing an efficient electricity network for [[Bohemia]]. The algorithm was rediscovered by [[Choquet]] in 1938; again by [[K._FlorekKazimierz Florek|Florek]], [[Jan Łukasiewicz|Łukasiewicz]], [[Julian Perkal|Perkal]], [[Hugo Steinhaus|Steinhaus]], and [[Stefan Zubrzycki|Zubrzycki]] in [[Hugo Steinhaus#graphs1951|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; <strike>[[Kazimierz Florek|Florek]] and his co-authors were anthropologists—thisanthropologists</strike>—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&#367;vka's algorithm is: