logo
SEE ALGORITHMS

Borůvka's Algorithm Visualization

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.

Pseudocode

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

Step by Step

  1. Initialize each vertex as its own isolated component (using Union-Find).
  2. Find the cheapest outgoing edge for every active component.
  3. Add all identified cheapest edges to the MST, deduplicating if two components pick the same edge.
  4. Merge (union) the connected components together.
  5. Repeat until only one component remains — the full MST.

Draw Graph
Union-Find

How It Works

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.

When to Use

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.

Time & Space Complexity

Metric / Operation
Complexity
Description
Sequential TimeO(E log V)Runs in at most log₂ V phases, with each phase inspecting all E edges.
Parallel TimeO(log² V)Cheapest-edge searches run in parallel across components on multi-core / GPU architectures.
Space ComplexityO(V + E)Stores the graph structure and Union-Find parent/rank arrays tracking components.

Common Interview Questions

How does Borůvka's algorithm differ fundamentally from Prim's and Kruskal's algorithms?

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.

What is the time complexity of Borůvka's algorithm and why is it well-suited for GPUs & parallel compute?

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.

What happens in Borůvka's algorithm if edge weights are not distinct, and how can cycle creation be prevented?

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.


💬  Discussion

to join the discussion


Curious to Learn More?

Hand-picked resources to deepen your understanding


Learn DSA on Udemy
Learn DSA on Udemy
As an Udemy Associate, I earn from qualifying purchases.

© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0