Grow one tree
Prim builds a minimum spanning tree by growing a single tree outward from a starting node. At each step it adds the cheapest edge that crosses from the tree to a node not yet in the tree.
Heap of crossing edges
To find that cheapest crossing edge quickly, Prim keeps a priority queue. Each unvisited node stores the smallest weight of any edge connecting it to the current tree. The algorithm pops the node with the smallest such key, adds it to the tree, then relaxes its edges to update neighbor keys.
- Pop the unvisited node with the smallest connection cost.
- Add it to the tree.
- For each neighbor still outside, lower its key if this edge is cheaper.
This mirrors Dijkstra's structure, but the key stored is the single edge weight rather than an accumulated path cost.
Key idea
Prim grows one tree and uses a priority queue to repeatedly attach the cheapest edge crossing into the unvisited set, storing each node's best single connecting edge weight as its key.