AlgoScope

Boruvka

Every component picks its cheapest outgoing edge simultaneously. Components halve each round.

Minimum spanning tree, algorithm, advanced
Round 1: 5 edges picked by 6 components.43124265001122334455
Round 1: 5 edges picked by 6 components.43124265001122334455

Minimum Spanning Tree: Boruvka: every component picks at once

Decision, step 2 of 4

Round 1: 6 components. Each picks its cheapest edge to another component: component 0 picks 0-2 (3), component 1 picks 1-2 (1), component 2 picks 1-2 (1), component 3 picks 1-3 (2), component 4 picks 3-4 (2), component 5 picks 2-5 (5). 5 distinct edges, because two components often pick the same one.

How minimum spanning tree works

Cost

Best
O(E log V)
Average
O(E log V)
Worst
O(E log V)
Space
O(V)

Taught by the same lesson

Minimum Spanning Tree covers these too, in the same run.