Grow a minimum spanning tree from one node: repeatedly add the cheapest edge that connects the tree to a node outside it. A min-heap keyed by each outside node’s cheapest link finds that edge quickly.
- Average time
- O(E log V)
- Space
- O(V + E)
Grow a minimum spanning tree from one node: repeatedly add the cheapest edge that connects the tree to a node outside it. A min-heap keyed by each outside node’s cheapest link finds that edge quickly.