Borůvka's algorithm: Difference between revisions

Revision as of 15:17, 25 June 2004

Revision as of 06:16, 5 October 2004

Line 2:

'''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 efficiently electrifying [[Bohemia]].

Bor&#367;vka's algorithm, in pseudocode, given a graph <math>''G</math>'', is:

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

*While <math>''L</math>'' is not connected (e.g.that is, it is a forest of more than one tree):

**For each subtreetree <math>''T</math>'' in <math>''L</math>'', find the smallest edge in <math>''G</math>'' connecting a vertex in <math>''T</math>'' to one outside it.

***Add that edge to <math>''L</math>'', reducing the number of trees in <math>''L</math>'' by one.

Bor&#367;vka's algorithm can be shown to run in time [[Big O notation|O]](<math>''E</math> ''log <math>''V</math>''), where <math>''E</math>'' is the number of edges, and <math>''V</math>'' is the number of vertices in <math>''G</math>''.

Other algorithms for this problem include [[Prim's algorithm]] 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:Graph algorithms]]