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 Classification
Design Technique Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 2 Connections
In Field
Source Wikipedia: Boruvka's algorithm
Uses Design Technique
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
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).
- Boruvka: "is a greedy algorithm for finding a minimum spanning tree"
In Field: Algorithms and Complexity Theory, Lead sentence
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected.
View the Source2. Boruvka's Algorithm (Wikipedia)
Wikipedia infobox: time complexity linearithmicQuote, Wikipedia infobox: time complexity linearithmic
linearithmic
Reader 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.