|
|
|
|
|
Boruvka's AlgorithmBorůvka's algorithm is an algorithm for finding minimum spanning trees. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Bohemia. Borůvka's algorithm, in pseudocode, given a graph G, is: - Copy the vertices of G into a new graph, L, with no edges.
- While L is not connected (that is, it is a forest of more than one tree):
- For each tree T in L, find the smallest edge in G connecting a vertex in T to one outside it.
- Add that edge to L, reducing the number of trees in L by one.
Borůvka's algorithm can be shown to run in time O(Elog V), where E is the number of edges, and V is the number of vertices in G. 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ůvka's. A faster randomized version of Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected time. The best known minimum spanning tree algorithm by Bernard Chazelle is based on Borůvka's and runs in O(E α(V)) time, where α is the inverse of the Ackermann function.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|