AlgoScope

Prim

Grow one tree from a start vertex, always adding the cheapest edge that leaves it.

Minimum spanning tree, algorithm, intermediate
Edge 0 to 2 weight 3 brings 2 into the tree.43124265012345
Edge 0 to 2 weight 3 brings 2 into the tree.43124265012345

Minimum Spanning Tree: Prim, growing from 0

Decision, step 2 of 7

Edges leaving the tree: 0-2 (3), 0-1 (4). The cheapest is 0-2 at 3, so 2 joins the tree. Total 3.

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.