Prim's Spanning Tree
Graphs: lesson 11 of 16
One tree that grows, always by its cheapest way out.
Lesson 11 of 16 · 6 min
Prim's Spanning Tree
Step 1 of 7
Start the tree at a. Its two exits go on the heap — the frontier is every way out of what you already own.
The Idea
Prim grows a single tree instead of merging scattered pieces. Every edge leaving the tree sits in a min-heap; pop the cheapest, and if its far end is new, absorb it and push that node's own exits. Stale edges — both ends already inside — are skipped on the way out. Same total as Kruskal, different order of arrival.
Real-World Example
A pipeline crew that has to stay connected to the depot. They cannot start a second, separate stretch of pipe in a far field, so each morning they extend the run they already have by the cheapest joint available.
The Code
import heapq
g = {"a": [("b", 1), ("c", 3)], "b": [("a", 1), ("c", 4), ("d", 5)],
"c": [("a", 3), ("b", 4), ("d", 2)], "d": [("b", 5), ("c", 2)]}
seen = {"a"}
pq = [(w, "a", m) for m, w in g["a"]]
heapq.heapify(pq)
total, tree = 0, []
while pq:
w, u, v = heapq.heappop(pq) # cheapest edge leaving the tree
if v in seen:
continue # both ends inside: stale
seen.add(v)
tree.append((u, v))
total += w
for m, w2 in g[v]:
if m not in seen:
heapq.heappush(pq, (w2, v, m))
print(tree, total) # [('a', 'b'), ('a', 'c'), ('c', 'd')] 6Your turn
What does this print?
import heapq
pq = [(3, "c"), (1, "b")]
heapq.heapify(pq)
print(heapq.heappop(pq))Mini quiz
1 / 3