Graphs You Never Build
Graphs: lesson 14 of 16
Generate the neighbours on demand and BFS works the same.
Lesson 14 of 16 · 6 min
Graphs You Never Build
Step 1 of 11
Nothing is stored but a set of words. There is no adjacency list, because the neighbours will be invented on demand.
The Idea
A graph does not have to exist in memory. If a rule tells you which states follow a state, BFS can walk it exactly as before: pop a state, generate its neighbours, keep the unseen ones. Word ladders, puzzle boards and lock combinations are all graphs that are cheaper to compute than to store.
Real-World Example
A password rotation tool checking how few single-character edits separate a new secret from a leaked one. Nobody stores the graph of all strings — it is astronomically large. The neighbours are generated one edit at a time, only along the path actually explored.
The Code
from collections import deque
words = {"cold", "cord", "card", "ward", "warm", "wolf"}
q = deque([("cold", 1)])
seen = {"cold"}
steps = 0
while q:
word, d = q.popleft()
if word == "warm":
steps = d
break
for i in range(len(word)): # neighbours are computed,
for ch in "abcdefghijklmnopqrstuvwxyz": # never stored
nxt = word[:i] + ch + word[i + 1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
q.append((nxt, d + 1))
print(steps) # 5: cold, cord, card, ward, warmYour turn
What does this print?
w = "cat"
neighbours = {w[:i] + c + w[i + 1:] for i in range(3) for c in "abc"}
print(len(neighbours))Mini quiz
1 / 3