Borůvka's Algorithm

Borůvka's algorithm

Borůvka's Algorithm

Borůvka's algorithm builds a minimum spanning tree in rounds.
In each round, each component selects the cheapest edge leading to another component, and all such edges are added to the MST simultaneously.

Idea of the Algorithm

• Initially, each vertex is a separate component.
• In one round, each component:
  • finds the minimum outgoing edge;
  • adds it to the MST.
• After that, the components are merged.
• The number of components decreases by at least half, so there are only $O(\log V)$ rounds.

Steps of the Algorithm

1. Initialization
   Each vertex forms its own component.

2. One round

   • For each component, find the minimum edge connecting it to another component.
   • Add all found edges to the MST.
   • Merge the components connected by these edges.

3. Repetition
   Repeat rounds until only one component remains.

4. Result
   All added edges form a minimum spanning tree.

Visualization

Complexity

• Each round: iterating over all edges — $O(E)$