Boruvka's algorithm finds a minimum spanning tree of a connected, weighted graph by repeatedly having every component in the current forest select its own cheapest outgoing edge and adding all selected edges to the forest simultaneously, merging components in each round until only one component remains. Otakar Boruvka published the technique in 1926 to solve an electrical network design problem, making it the earliest known minimum spanning tree algorithm, predating both Kruskal's and Prim's algorithms. It runs in O(E log V) time and is well suited to parallel implementation because every component's edge selection in a round is independent of the others.
Facts
Time Complexity Sources
1. Wikipedia: Boruvka's algorithm
Lead section
It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.
Pseudocode and complexity section
Borůvka's algorithm can be shown to take O(log V) iterations of the outer loop until it terminates, and therefore to run in time O(E log V), where E is the number of edges, and V is the number of vertices in G (assuming E ≥ V).
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.