Connecting at least cost
A minimum spanning tree, or MST, connects every vertex of a weighted undirected graph using a set of edges whose total weight is as small as possible and which forms no cycle. Prim's algorithm grows that tree from a single seed vertex.
Growing one tree
- Start with any single vertex as the initial tree.
- Look at all edges that cross from the tree to a vertex outside it.
- Choose the cheapest such crossing edge and add its outside vertex to the tree.
- Repeat until every vertex has joined.
A min heap keyed on the cheapest connecting edge per outside vertex makes the choice efficient. Each time a vertex joins, you update its neighbours' best connecting cost.
Why the greedy choice is safe
The cut property guarantees correctness: for any way of splitting the vertices into two groups, the lightest edge crossing that split belongs to some MST. Prim always adds exactly such a lightest crossing edge, so it never makes a wrong move.
Prim's heap based form runs well on dense graphs, while Kruskal's edge sorting approach often suits sparse ones.
Key idea
Prim grows a single tree by repeatedly adding the cheapest edge that reaches a new vertex, and the cut property proves each such greedy choice is part of a minimum spanning tree.