Boruvka's Algorithm Calculator

Pseudocode

Every component picks its own cheapest outgoing edge, and all those picks are applied at once. Rounds rather than steps, which is what makes it parallelisable.

Boruvka(graph):
    makeSet(v) for every vertex
    mst = []

    while more than one component remains:
        cheapest = {} // per component
        for each edge (u, v, w):
            a = find(u); b = find(v)
            if a == b: continue         // internal edge
            if w < cheapest[a]: cheapest[a] = (u,v,w)
            if w < cheapest[b]: cheapest[b] = (u,v,w)

        for each edge e in cheapest.values():
            if find(e.u) != find(e.v):  // may already be merged
                union(e.u, e.v); mst.append(e)

The inner guard on the second loop is essential, not defensive. Two components frequently choose the same edge, one from each end, and applying it twice would add a duplicate. Correctness needs edge weights to be distinct, or a consistent tie-break such as comparing edge ids: without one, several components can each pick a different edge of equal weight and together form a cycle.

Worked example, step by step

Build the minimum spanning tree on the same graph used for Prim and Kruskal, so all three can be compared.

Example graph: Undirected edges A-B (2), A-C (3), B-C (1), C-D (4) and B-D (7).

1. Start. Every vertex is its own component: {A}, {B}, {C}, {D}. Every edge is therefore outgoing for both of its endpoints.
2. Each component picks. Component A compares A-B at 2 against A-C at 3 and picks A-B. Component B compares A-B at 2, B-C at 1 and B-D at 7, picking B-C. Component C compares A-C at 3, B-C at 1 and C-D at 4, picking B-C. Component D compares C-D at 4 against B-D at 7 and picks C-D.
3. Note the duplicate. B and C both nominated the same edge B-C, once from each end. The guard on the second loop applies it a single time, which is exactly why that check exists.
4. Apply all picks at once. Adding A-B, B-C and C-D merges everything into one component in a single round. That is three edges for four vertices, so the tree is already complete.
5. Loop terminates. Only one component remains, so no second round runs.

The minimum spanning tree is A-B, B-C and C-D with total weight 2 + 1 + 4 = 7, the same tree Prim and Kruskal produced. Boruvka got there in one round rather than three sequential steps, which is the point: each round at least halves the number of components, since every component merges with at least one other, so only O(log V) rounds are ever needed.

Complexity, and where it comes from

Time: O(E log V) · Space: O(V + E)

Each round scans every edge once at O(E) to find the cheapest outgoing edge per component. Every component merges with at least one other during a round, so the component count at least halves, meaning at most log base 2 of V rounds occur. Multiplying gives O(E log V), matching Prim and Kruskal. The distinguishing property is that within a round every component works independently, so the scan parallelises directly, which is why Boruvka underlies GPU and distributed MST implementations while Prim and Kruskal, both inherently sequential, do not. Hybrid algorithms run a few Boruvka rounds to shrink the graph and then switch to Prim.

When to use Borůvka's Algorithm, and when not to

All three classical MST algorithms cost O(E log V). The difference is structural.

Common pitfalls

• Not handling tied edge weights. With equal weights, different components can pick different edges that together close a cycle, and the result is not a tree. Break ties consistently, for example by edge index, so that all components agree on an ordering. Distinct weights make the problem disappear.
• Adding the same edge twice. Two components routinely nominate the same edge from opposite ends. Without a check that the endpoints are still in different components at apply time, the edge is added twice and the edge count exceeds V - 1.
• Recomputing components inside the edge scan. Calling find repeatedly without path compression makes each round far more expensive than O(E). Use Union-Find with both path compression and union by rank, exactly as in Kruskal.
• Assuming it needs a connected graph. Like Kruskal, Boruvka handles disconnected input naturally, returning a minimum spanning forest. The loop condition must then be "no component has an outgoing edge" rather than "one component remains", or it will not terminate.
• Overlooking that it predates the others. Published in 1926 to plan an electricity network in Moravia, Boruvka is the oldest known MST algorithm, older than both Prim and Kruskal. It is often taught last, which obscures that the parallel formulation came first.

Frequently asked questions

How does Boruvka's algorithm work?

Every component simultaneously selects the cheapest edge leaving it, and all selected edges are added at once, merging components. This repeats until a single component remains. Because each component merges with at least one other per round, the number of components at least halves each time and only O(log V) rounds are needed.

What is the time complexity of Boruvka's algorithm?

O(E log V). Each round scans all E edges to find the cheapest outgoing edge per component, and at most log V rounds occur because the component count halves each round. This matches Prim and Kruskal asymptotically.

Why is Boruvka's algorithm good for parallel computing?

Because within a round each component determines its own cheapest outgoing edge independently, with no shared state and no ordering requirement. That maps directly onto GPUs and distributed clusters. Prim and Kruskal are inherently sequential: each depends on the single global choice made immediately before.

Why do edge weights need to be distinct?

With tied weights, different components can select different edges of equal cost that together form a cycle, so the result is not a tree. Any consistent tie-break, such as comparing edge indices when weights are equal, restores correctness. Distinct weights also make the minimum spanning tree unique.

What is the difference between Boruvka, Prim and Kruskal?

All three produce a minimum spanning tree in O(E log V). Prim grows one tree from a start vertex using a priority queue. Kruskal sorts all edges and adds any that does not close a cycle. Boruvka has every component pick its cheapest outgoing edge in parallel rounds, which is the only one of the three that parallelises naturally.