Overview
Boruvka's algorithm starts with each vertex as its own component, finds the cheapest edge leaving every component, adds those edges, and contracts the resulting components.
CoreSource checked
Boruvka's Algorithm
Builds a minimum spanning tree by repeatedly adding each component's cheapest outgoing edge.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Minimum Spanning Tree
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
minimum spanning tree constructionminimum spanning treeheap ordergraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use when MST construction can benefit from many components choosing edges in parallel.
- Use as a practical component-reduction phase before another MST algorithm.
When Not to Use
- Avoid on directed graphs; the standard method is for undirected MSTs.
- Avoid when identifying cheapest outgoing edges is expensive relative to the graph size.
What It Does
- Boruvka's Algorithm uses growing many tree components at once and repeatedly adding each component's cheapest outgoing edge for minimum spanning tree construction
- Organizes the work around minimum spanning tree construction and minimum spanning tree.
Use Cases
- Production and research workloads requiring minimum spanning tree via Builds a minimum spanning tree by repeatedly adding each component's cheapest outgoing edge.
- Minimum Spanning Tree pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
- Engineering comparisons against Reverse-Delete Algorithm and Minimum Spanning Tree when tuning minimum spanning tree.
Inputs
- Minimum Spanning Tree input instance for minimum spanning tree
- Configuration parameters controlling minimum spanning tree construction
Outputs
- Computed minimum spanning tree solution produced by Boruvka's Algorithm
- Diagnostic state over minimum spanning tree construction and minimum spanning tree
Pseudocode
- 1.Initialize each vertex as its own component
- 2.While more than one component remains
- 3.For each component, find its cheapest outgoing edge
- 4.Add all chosen edges that connect different components
- 5.Union their endpoint components
- 6.Return the selected edges
Canonical Example
- Input
- vertices A,B,C with edges AB=1, BC=2, AC=5
- Output
- MST edges AB and BC
- Explanation
- Components first choose their cheapest outgoing edges, quickly merging into one tree.
Implementation Notes
- Use union-find to track components after each round.
- Scan edges to record the cheapest outgoing edge for each component.
- Add all selected edges for the round, then merge components.
Common Pitfalls
- Edges inside a component must be ignored when choosing outgoing edges.
- Multiple components can choose the same edge; union operations must handle duplicates.
- Disconnected input produces a forest unless handled as an error.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow growing many tree components at once and repeatedly adding each component's cheapest outgoing edge on a small minimum spanning tree construction example.
Step 1 of 6: Initialize each vertex as its own component
graph-traversal-mechanismNotes
Boruvka's rounds can shrink the number of components quickly, especially on sparse graphs.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Boruvka's Algorithm's algorithm family, complexity framing, and standard implementation concepts.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Boruvka's Algorithm in the graph, flow, matching, and combinatorial optimization benchmark area.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
UsesKruskal's Algorithm
Graph Traversal · Core
Boruvka's Algorithm uses Kruskal's Algorithm as a subroutine, representation, or supporting idea while growing many tree components at once and repeatedly adding each component's cheapest outgoing edge.
Compare with thisRelationships
View full relationship pageBoruvka's Algorithm uses Reverse-Delete Algorithm as a subroutine, representation, or supporting idea while growing many tree components at once and repeatedly adding each component's cheapest outgoing edge.
Boruvka's Algorithm uses Minimum Spanning Tree as a subroutine, representation, or supporting idea while growing many tree components at once and repeatedly adding each component's cheapest outgoing edge.
Boruvka's Algorithm uses Kruskal's Algorithm as a subroutine, representation, or supporting idea while growing many tree components at once and repeatedly adding each component's cheapest outgoing edge.
Tags
GraphTraversalPriority Queue