Boruvka
Every component picks its cheapest outgoing edge simultaneously. Components halve each round.
Minimum Spanning Tree: Boruvka: every component picks at once
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.
Cost
- Best
- O(E log V)
- Average
- O(E log V)
- Worst
- O(E log V)
- Space
- O(V)
Before this
Taught by the same lesson
Minimum Spanning Tree covers these too, in the same run.