Borůvka's algorithm: Difference between revisions

Revision as of 03:19, 22 July 2006

Revision as of 18:42, 21 December 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 [[Kazimierz 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, this algorithm is frequently 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: