Borůvka's Algorithm Visualization
Borůvka's Algorithm is a greedy approach to find a Minimum Spanning Tree (MST) in a graph. 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.
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.
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0