A minimum spanning tree (MST) is the cheapest set of edges that connects *every* vertex with no cycles — the least-cost way to wire a whole network together. Prim's algorithm builds it by growing a single tree outward: start anywhere, and keep absorbing the cheapest edge that reaches a vertex not yet in the tree.
Grow one connected blob
At every step the tree-so-far has a frontier: edges with one end inside the tree and one end outside. Prim picks the cheapest frontier edge, pulls its outside vertex in, and the frontier updates. It looks a lot like Dijkstra — but Prim judges each candidate edge by its own weight, not by total distance from a source.
1Pick any start vertex; the tree begins as just that one vertex.
2Look at all frontier edges — those crossing from the tree to a vertex outside it.
3Add the cheapest such edge, bringing its outside vertex into the tree.
4Update the frontier with that new vertex's edges, and repeat until all V vertices are joined.
A priority queue makes it fast
Keep the frontier edges in a min-heap keyed by weight, so the cheapest one is always ready to hand. That's what turns Prim into an O(E log V) algorithm rather than a repeated linear scan.
Why greedy is safe — the cut property
Split the vertices into 'in the tree' and 'out'. The single cheapest edge crossing that cut is *always* part of some MST. Prim adds exactly that edge each step, so it can never paint itself into a corner — every choice is provably safe.
OperationTimeSpace
With a binary heap · V vertices, E edges; one tree grown outwardO(E log V)O(V)
Check yourself
How does Prim's algorithm decide which edge to add next?
