11.6 Borůvka's Algorithm

Problem

Kruskal's algorithm grows a forest by processing edges globally. Prim's algorithm grows a single tree from a starting vertex.

Both approaches are highly effective, but neither was the first minimum spanning tree algorithm.

In 1926, before modern computers existed, the Czech mathematician entity["people","Otakar Borůvka","Czech mathematician"] developed an algorithm for designing an efficient electrical network. His solution became one of the earliest graph optimization algorithms and remains important today because of its natural parallelism.

The key idea is simple:

Every connected component simultaneously chooses its cheapest outgoing edge.

Instead of adding one edge at a time, Borůvka's algorithm can add many edges during a single iteration.

Solution

Initially, every vertex forms its own component.

During each phase:

1. For every component, find its cheapest outgoing edge.
2. Add all selected edges simultaneously.
3. Merge connected components.
4. Repeat until only one component remains.

The cut property guarantees that every selected edge is safe.

Example

Consider:

      4
A -------- B
|          |
|          |
1          5
|          |
|          |
C -------- D
      2

Additional edge:

A -------- D
      3

Initial Components

{A}
{B}
{C}
{D}

Cheapest Edge from Each Component

For:

A

choose:

A-C = 1

For:

B

choose:

A-B = 4

For:

C

choose:

A-C = 1

For:

D

choose:

C-D = 2

Selected edges:

A-C
A-B
C-D

After merging:

A
|\\n| \\nC  B
|
|
D

All vertices belong to one component.

The algorithm terminates.

Why the Cheapest Outgoing Edge Is Safe

Suppose component:

S

contains several vertices.

Everything outside the component belongs to:

V - S

This defines a cut.

The cheapest edge leaving the component is the minimum crossing edge of that cut.

By the cut property:

The minimum crossing edge is safe.

Therefore every component may safely select its cheapest outgoing edge.

This is the central theorem behind Borůvka's algorithm.

Parallel Growth

The most distinctive feature of Borůvka's algorithm is that many edges are added simultaneously.

Kruskal:

One edge
One decision

Prim:

One edge
One decision

Borůvka:

Many components
Many decisions
Many edges

This property makes the algorithm attractive for:

• Parallel computing
• Distributed systems
• GPU implementations
• Massive graph processing

Component Reduction

An important observation:

Every component selects at least one outgoing edge.

Therefore every phase merges components.

In fact, the number of components is at least halved during each iteration.

Example

Suppose:

64 components

After one phase:

≤ 32

After another:

≤ 16

Then:

≤ 8
≤ 4
≤ 2
≤ 1

Only:

$$ \log_2 V $$

phases are required.

This observation drives the complexity analysis.

Detailed Example

Graph:

A-B = 3
A-C = 1
B-D = 2
C-D = 4
D-E = 5
C-E = 6

Phase 1

Components:

A
B
C
D
E

Cheapest outgoing edges:

A → C (1)
B → D (2)
C → A (1)
D → B (2)
E → D (5)

Selected:

A-C
B-D
D-E

Components become:

{A,C}
{B,D,E}

Phase 2

Component:

{A,C}

Cheapest outgoing:

A-B = 3

Component:

{B,D,E}

Cheapest outgoing:

A-B = 3

Add:

A-B

All vertices become connected.

Algorithm terminates.

Union-Find Implementation

Borůvka relies heavily on union-find.

For every edge:

(u,v)

determine:

find(u)
find(v)

If they belong to different components:

find(u) != find(v)

the edge is a candidate outgoing edge.

Maintain:

cheapest[component]

During each phase.

After processing all edges:

union(...)

merges selected components.

Pseudocode

Boruvka(G):

    make_set(v)

    components = V

    while components > 1:

        cheapest = empty

        for each edge(u,v,w):

            c1 = find(u)
            c2 = find(v)

            if c1 == c2:
                continue

            update cheapest edge
            for c1 and c2

        for each chosen edge:

            if components differ:

                add edge to MST
                union(...)
                components--

This is the standard implementation.

Correctness Proof

The proof follows directly from the cut property.

For each component:

1. The component defines one side of a cut.
2. Its cheapest outgoing edge is the minimum crossing edge.
3. The cut property guarantees safety.
4. All selected edges are safe.
5. Repeated merging eventually produces a spanning tree.

Therefore Borůvka constructs a minimum spanning tree.

Time Complexity

Let:

$$ V = \text{vertices} $$

$$ E = \text{edges} $$

Per Phase

Inspect every edge:

$$ O(E) $$

Number of Phases

At most:

$$ O(\log V) $$

because components at least halve each phase.

Total

$$ O(E \log V) $$

This matches the complexity of efficient Prim implementations.

Space Complexity

Store:

• Edge list
• Union-find
• Cheapest outgoing edge array

Memory:

$$ O(V + E) $$

Comparison with Kruskal

Property	Borůvka	Kruskal
Edge sorting	Not required	Required
Uses union-find	Yes	Yes
Parallel phases	Yes	No
Component growth	Simultaneous	Sequential
Complexity	O(E log V)	O(E log E)

Borůvka avoids global sorting.

For very large graphs this can be advantageous.

Comparison with Prim

Property	Borůvka	Prim
Multiple components	Yes	No
Priority queue	No	Yes
Parallelism	Excellent	Limited
Dense graph performance	Moderate	Strong

Prim tends to dominate on dense graphs.

Borůvka shines on distributed and parallel systems.

Hybrid Algorithms

Many industrial MST implementations combine algorithms.

A common strategy:

1. Run several Borůvka phases.
2. Greatly reduce the number of vertices.
3. Finish with Kruskal or Prim.

This approach often outperforms any single algorithm alone.

Modern graph-processing frameworks frequently use such hybrids.

Common Mistakes

Forgetting Component Boundaries

The cheapest edge must leave the component.

Internal edges are irrelevant.

Adding Duplicate Edges

Two components may choose the same edge.

Careful union-find checks prevent duplicates.

Updating Cheapest Edges Incorrectly

Each component needs its own cheapest outgoing edge.

A global minimum is not sufficient.

Ignoring Parallel Merges

Several merges occur simultaneously.

Sequential reasoning can lead to implementation errors.

Real-World Applications

Electrical Network Design

The original application that motivated the algorithm.

Distributed Graph Processing

Large graph analytics systems.

Parallel Computing

Multi-core MST construction.

Geographic Infrastructure Planning

Road, pipeline, and utility networks.

Massive Graph Databases

Graphs too large for efficient global sorting.

Recipe

When applying Borůvka's algorithm:

1. Start with every vertex as its own component.
2. Find the cheapest outgoing edge for every component.
3. Add all selected edges.
4. Merge connected components.
5. Repeat until one component remains.
6. The selected edges form a minimum spanning tree.

Borůvka's algorithm completes the trio of classical minimum spanning tree algorithms. The next section introduces the union-find data structure in depth, the component-management structure that powers both Kruskal's algorithm and many advanced connectivity algorithms.