Lesson 27.2 · Minimum Spanning Trees
Prim's Algorithm
Grow one tree from any node, always adding the cheapest edge that leaves it. A heap gives O(E log V); a plain array gives O(V²), best for dense graphs.
12 min
Think of it like this
A water company expanding from its pumping station: each step it lays the cheapest pipe from the current network to a house not yet connected.
1.Two implementations
Heap version: like Dijkstra, but the key of a node is the weight of the single cheapest edge connecting it to the tree, not a path length. Pop the smallest, add it to the tree, push its edges. O(E log V).
Array version: keep best[v] = cheapest edge from the tree to v. Each step, scan for the cheapest outside node (O(V)), add it, and update best with its edges. O(V²) total with no heap. When every pair of points is an edge (E ≈ V²/2), this beats both Kruskal and heap Prim.
2.Kruskal or Prim?
Edge list given, sparse graph: Kruskal (sort + union-find), shortest to write. Complete graph from points: array Prim, which never builds the edge list. Both give the same total weight; the trees may differ if weights tie.
Remember
- Prim's key = cheapest edge into the tree.
- Dense graphs: O(V²) array Prim.
- Same total as Kruskal.
Common mistakes
- Adding the path distance (that's Dijkstra) instead of the edge weight.