Borůvka's Algorithm

An interactive, step-by-step visualisation of Borůvka's Algorithm.

Category: Graphs
Time complexity: O(E log V)
Space complexity: O(V)

Pseudocode

while more than one component:
  each component picks its cheapest outgoing edge
  merge all chosen edges at once
repeat

Reference implementation

while len(components) &gt; 1:
    cheapest = {}
    for u, v, w in edges:
        if find(u) != find(v):
            update_if_cheaper(cheapest, u, v, w)
    for edge in cheapest.values(): union(edge)

Open the interactive Borůvka's Algorithm visualisation →