Prim
Grow one tree from a start vertex, always adding the cheapest edge that leaves it.
Minimum Spanning Tree: Prim, growing from 0
Edges leaving the tree: 0-2 (3), 0-1 (4). The cheapest is 0-2 at 3, so 2 joins the tree. Total 3.
Cost
- Best
- O(E log V)
- Average
- O(E log V)
- Worst
- O(E log V)
- Space
- O(V)
Before this
Related
Taught by the same lesson
Minimum Spanning Tree covers these too, in the same run.