Borůvka's algorithm: Difference between revisions

Revision as of 10:18, 1 April 2006

Revision as of 10:19, 1 April 2006

Line 3:

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 continescontinues joining these groupinggroupings 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:

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