Kruskal
Sort the edges by weight and take each one that joins two different components, which union-find answers.
Minimum Spanning Tree: Kruskal, cheapest edges first
Edge 1-2, weight 1. 1 is in component 1 and 2 in component 2, different, so take it: they merge and the total is 1.
Cost
- Best
- O(E log E)
- Average
- O(E log E)
- Worst
- O(E log E)
- Space
- O(V)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Minimum Spanning Tree covers these too, in the same run.