Borůvka's algorithm: Difference between revisions

Revision as of 19:30, 2 June 2004

Revision as of 17:00, 4 June 2004

Line 1:

'''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ůvka's algorithm''' finds [[minimum spanning tree|minimum spanning trees]]. A minimum spanning tree is a tree containing each vertex in the graph such that the sum of the edges' weights is minimum. Each vertex in the graph finds its lightest edge, then the vertices at the ends of each lightest edge are identified. This continues until the entire graph collapses into a single point. The tree consists of all the lightest edges so found.

Bor&#367;vka's algorithm can be shown to run, in time O(m log n)pseudocode, wheregiven ma isgraph the number of edges<math>G</math>, and n is the number of vertices.:

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

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 algorithm due to Karger, Klein and Tarjan runs in expected O(m) time, where m is the number of edges in the graph.

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

**For each subtree <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 algorithm due to Karger, Klein and Tarjan runs in expected <math>O(mE)</math> time, where m is the number of edges in the graph.

[[Category:Graph algorithms]]