Grow one blob outwards
Prim's MST
The analogy
Rather than considering all cables globally, start at one building and grow a single connected blob. Each step, look at every cable leaving the blob and take the cheapest one that reaches a new building. The blob only ever grows, and it is always connected.
Visualizer
Growing one blob
step 1 / 8Prim starts at one town and grows a single connected blob. Candidate edges out of A: A-B (4) and A-C (2).heap: (2,C), (4,B)
import heapq
def prim(g, start=0):
visited = set()
pq = [(0, start)]
total, edges = 0, 0
while pq and len(visited) < len(g):
w, u = heapq.heappop(pq)
if u in visited:
continue # stale entry
visited.add(u) # mark on POP
total += w
for v, wt in g[u]:
if v not in visited:
heapq.heappush(pq, (wt, v)) # key = EDGE weight,
# not accumulated dist
return total
# O(E log V). Compare Dijkstra: nd = d + w <- accumulatesCheck yourself
What is the one line that differs between Prim and Dijkstra?