Borůvka's Algorithm is the oldest known Minimum Spanning Tree (MST) algorithm, invented by Otakar Borůvka in 1926. It works by repeatedly selecting the cheapest edge connecting two components and adding all such edges at once. By merging multiple components in every iteration, the algorithm quickly reduces the number of components until the entire graph becomes a single connected tree.
for each vertex v:
create a component {v}while components > 1:
for each component C:
find cheapest edge leaving C
add all cheapest edges to MST
merge connected components
Borůvka's algorithm begins with every vertex as an independent tree component. In each phase, every component identifies its lowest-weight edge connecting it to an outside component. All selected minimum edges are simultaneously added to the MST, and connected components are merged using a Union-Find data structure. Because every component is guaranteed to merge with at least one other component during each phase, the total number of components decreases by at least half each time, guaranteeing termination in at most log₂ V phases.
Borůvka's algorithm is uniquely well-suited for parallel and distributed computing (such as GPUs, multi-core clusters, and MapReduce). Unlike Prim's algorithm (which expands a single component one edge at a time), Borůvka's components evaluate their cheapest edges independently without shared state conflicts, allowing massive concurrency across thousands of cores.
Metric / Operation | Complexity | Description |
|---|---|---|
| Sequential Time | O(E log V) | Runs in at most log₂ V phases, with each phase inspecting all E edges. |
| Parallel Time | O(log² V) | Cheapest-edge searches run in parallel across components on multi-core / GPU architectures. |
| Space Complexity | O(V + E) | Stores the graph structure and Union-Find parent/rank arrays tracking components. |
Borůvka's algorithm is a parallel-friendly algorithm. In each phase, every connected component simultaneously finds its cheapest outgoing edge. All identified minimum edges are added to the MST at once, reducing the number of components by at least half each iteration.
Borůvka's algorithm runs in O(E log V) time. Because each component searches for its minimum outgoing edge independently of other components, these searches can be executed concurrently in parallel threads across multiple GPU cores.
If two edges have identical minimum weights, two components might simultaneously pick edges that together create a cycle instead of an acyclic tree. To prevent this, a consistent tie-breaking rule is enforced, such as comparing unique edge IDs or vertex index tuples (u, v) — ensuring all edge weights are effectively strictly distinct.
to join the discussion
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0