ƒ(x) GraphAdvanced interactive
Prim's MST
Grow a minimum spanning tree one edge at a time.
graph_prim
step 1 / 12
Start Prim's at A. Grow one cheapest crossing edge at a time.
candidatecurrentin treeMST edge
speed1×
How it works
Prim's algorithm builds a minimum spanning tree by starting from any node and repeatedly adding the cheapest edge that connects the tree to a new vertex. A min-heap over crossing edges makes each choice efficient, yielding the lowest-cost tree that connects every node.
Mental models
- The cut property: the cheapest edge crossing any cut is always safe to add.
- Greedy and never backtracks — every added edge stays in the final tree.
Common pitfalls
- For dense graphs it edges out Kruskal; for sparse ones Kruskal is often simpler.
Complexity
- Time
- O(E log V)binary heap
- Space
- O(V + E)
Reach for it when
- Network / cable layout
- Clustering
- Approximating TSP