Boruvka's Minimum Spanning Tree

Boruvka's algorithm is the oldest known way to build a minimum spanning tree (MST) — the cheapest set of edges that connects every vertex of a weighted graph. It is beautifully parallel: instead of growing one tree edge by edge, every component grabs its own cheapest exit at the same time.

The slow way first

You could try every possible spanning tree and keep the cheapest — but the number of spanning trees explodes exponentially, so that is hopeless for anything but tiny graphs.

The question to ask: what edge is definitely safe to add? There is a classic guarantee — for any component (group of already-connected vertices), the cheapest edge leaving it is always part of some MST. So instead of guessing whole trees, we can keep grabbing safe edges.

The idea: every component grabs its cheapest exit

Start with each vertex as its own component. Then repeat rounds:

1. For every component, scan its edges and find the single cheapest edge that leads to a different component.
2. Add all of those chosen edges at once and union the components they connect.
3. Stop when only one component is left.

Because every component shrinks the count by at least half each round, only O(log n) rounds are needed.

Walk through it

Step through the animation. In round 1, every lonely vertex picks its cheapest edge — that gives A-D(5), B-E(4), C-F(2), and E-F(3), collapsing six components into two: {A, D} and {B, C, E, F}. In round 2, the two groups look at the edges crossing between them and both pick the cheapest, D-E(6). That merges everything into one component, so we stop. Total MST weight: 20.

Pseudocode

put every vertex in its own component (union-find)
total = 0
while more than one component remains:
    cheapest[c] = none   for every component c
    for each edge (w, u, v):
        if u and v are in the same component: skip
        for each endpoint's component r:
            if this edge is cheaper than cheapest[r]: cheapest[r] = edge
    for each chosen cheapest edge:
        if its endpoints are still in different components:
            union them and add its weight to total
return total

The Python solution

def boruvka(n, edges):          # edges: (w, u, v)
    uf = UnionFind(n)
    total = 0
    while uf.components > 1:
        cheapest = [None] * n       # best edge per component
        for w, u, v in edges:
            ru, rv = uf.find(u), uf.find(v)
            if ru == rv:
                continue            # same component, skip
            for r in (ru, rv):
                if cheapest[r] is None or w < cheapest[r][0]:
                    cheapest[r] = (w, u, v)
        for e in cheapest:
            if e and uf.union(e[1], e[2]):
                total += e[0]
    return total

• uf is a union-find structure: find returns a vertex's component id, union merges two and reports whether they were actually different.
• The while loop runs once per round and keeps going until everything is one component.
• cheapest[r] holds the lightest outgoing edge found so far for component r.
• The first inner loop scans every edge; an edge inside one component (ru == rv) is skipped, otherwise it may update the cheapest for both endpoints' components.
• The second loop commits the picks: uf.union returns True only when the two ends were still separate, which prevents adding the same edge twice or forming a cycle.

Complexity

The component count drops by at least half each round because every component merges with at least one other, so there can be at most O(log n) rounds, each scanning all E edges.

When this pattern shows up

Practice