A minimum spanning tree connects every node of a weighted graph using the edges of smallest total weight. Kruskal's algorithm takes the lightest edges anywhere in the graph, so its pieces grow separately and merge. Prim's algorithm keeps one tree from the start and grows it outwards:
It's safe for the same reason as Kruskal: some edge has to connect the tree to the rest of the graph, and the lightest such edge can always be part of a minimum spanning tree.
Scanning every edge leaving the tree at each step would be slow. Instead, every node outside the tree has a key: the weight of the lightest edge known to connect it to the tree (∞ if none). When a node joins, check its edges: if edge u–v is lighter than v's key, v's key drops to that weight. The next node to join is the one with the smallest key, which is a job for a min-priority queue.
If that sounds like Dijkstra's algorithm, it is: the structure is identical. The one difference is the update rule:
| Dijkstra | Prim | |
|---|---|---|
| A node's number is | the length of the best path from the start | the weight of the best single edge to the tree |
| Checking edge u–v (weight w) | new distance = min(dist(v), dist(u) + w) | new key = min(key(v), w) |
| Result | a shortest-path tree | a minimum spanning tree |
A key ∞ B has a key: waiting in the queue C just joined D in the tree
Numbers under the nodes are their keys. Solid blue edges are in the tree; dashed blue edges are the edges behind the current keys. Ties are broken alphabetically, and a key only changes when an edge is strictly lighter, so each question has one right answer.
| Prim | |
|---|---|
| Time | O((V + E) log V) with a binary heap |
| Prim or Kruskal? | Both give a minimum tree. Prim suits dense graphs and adjacency lists; Kruskal suits sparse graphs given as a list of edges. |