Edge List
A flat list of (u, v, weight) triples, the natural input for Kruskal, which sorts it by weight.
Minimum Spanning Tree: Kruskal, cheapest edges first
Kruskal: sort the 8 edges by weight, 1-2 (1), 1-3 (2), 3-4 (2), 0-2 (3), 0-1 (4), 2-3 (4), 2-5 (5), 4-5 (6), and take each one unless its ends are already connected. Each vertex shows its component. Two vertices with the same number are already joined, so an edge between them would close a cycle.
Cost
- Edge lookup
- O(E)
- Add edge
- O(1)
- Sort edges
- O(E log E)
- Space
- O(E)
Related
Taught by the same lesson
Minimum Spanning Tree covers these too, in the same run.