Graph problems rarely say graph
Interviews and real systems hand you stories, not adjacency lists, so the skill is translation. Three questions do most of the work.
- What are the nodes? The things: cities, words, tasks, grid squares.
- What are the edges? The relation: has a flight to, differs by one letter, must happen before, is adjacent to.
- What is the question in graph words? Fewest hops is a shortest path, solved by BFS from lesson 5-3. Can I reach X is connectivity. A valid order to do these is a topological sort, which belongs to the Algorithms course.
Take what is the fewest flights from SFO to JFK. Nodes are airports, edges are direct routes, and the question is a shortest path measured in hops.
BFS answers it directly, and the reason is the ring order. Because BFS finishes every airport at k hops before starting on k+1, the ring where JFK first appears is the answer, with no extra bookkeeping.
Even a maze is a graph. Every open square is a node and edges connect touching squares, so there are no pointers anywhere and it is still a graph.
That is the habit to build. The structure is usually implicit in the wording, and naming the nodes and edges out loud is what turns an unfamiliar story into an algorithm you already know.
Fewest flights with BFS
The dist dict records hop counts and doubles as the seen set.
from collections import deque def shortest_hops(adj, start, goal): frontier = deque([start]) dist = {start: 0} while frontier: node = frontier.popleft() if node == goal: return dist[node] for neighbor in adj[node]: if neighbor not in dist: dist[neighbor] = dist[node] + 1 frontier.append(neighbor) return -1 flights = { "SFO": ["LAX", "DEN"], "LAX": ["SFO", "DFW"], "DEN": ["SFO", "ORD", "DFW"], "DFW": ["LAX", "DEN", "JFK"], "ORD": ["DEN", "JFK"], "JFK": ["DFW", "ORD"], } print(shortest_hops(flights, "SFO", "JFK")) print(shortest_hops(flights, "SFO", "LAX")) print(shortest_hops(flights, "JFK", "SFO"))
Output
3 1 3
This is lesson 5-3's loop with two changes. The goal is checked right after popping, and one dist dict replaces the separate seen set, since a node's presence in dist already means it has been reached.
New neighbors get dist[neighbor] = dist[node] + 1 before being enqueued, so the distance is fixed at discovery time rather than recomputed later.
The SFO to JFK path takes 3, and the rings show why. Ring 1 holds LAX and DEN, ring 2 adds DFW and ORD, and ring 3 reaches JFK.
The return -1 is the unreachable case, taken only when the frontier empties without the goal ever appearing. It matters for real route data, where an airport can sit in a disconnected cluster.
The third call runs the search backwards and also returns 3, which is expected here because these routes are listed in both directions. A directed graph of one-way flights could easily give different answers each way.
The nodes are words and the edges are pairs of words differing by exactly one letter, which makes the question whether a path exists.
The chain cold, cord, card, ward, warm is exactly a path through that graph, with each step crossing one edge because each step changes one letter.
Nothing in the wording mentions a graph, and the data arrives as a flat dictionary of words. The three questions are what uncover it: the things are words, the relation is a one-letter difference, and the ask is a path.
BFS then gives more than a yes. Since it explores ring by ring, the ring in which warm first appears is the fewest single-letter changes possible, so the same code answers both the existence and the minimum.
Building the edges is the only real work. Comparing every pair of words is O(n²) in the dictionary size, which is why practical solutions group words by wildcard patterns like c_ld instead, using the grouping idiom from lesson 6-3.
The check is needed because flight routes loop, so without it BFS would re-enqueue nodes forever.
The cycle is right there in the data. SFO lists LAX and LAX lists SFO, so an unguarded search would enqueue LAX from SFO, then enqueue SFO from LAX, and bounce between them without end.
Marking a node the first time it is reached does two jobs at once. It prevents the loop, and it locks in the node's shortest distance, because BFS necessarily reaches every node in the earliest possible ring.
That second job is why a later, longer route to the same node must be ignored rather than recorded. Overwriting dist[neighbor] on a second sighting would replace a correct shortest distance with a worse one.
This is also the difference from tree traversal in lesson 7-2, which needed no such check. A tree has no cycles by definition, so the guard exists purely because graphs are the general case.
Those edges are prerequisite arrows, which makes the graph directed.
Advanced Python before Data Structures points one way only, and the reverse statement is false, so a single arrow captures it while an unordered pair would not.
Friendship is the contrasting case. It is mutual, so an undirected edge is the honest encoding, which is why lesson 9-1's builder recorded each friendship in both directions.
Prerequisite graphs also carry a second property worth noticing. They must have no cycles, since a cycle would mean a course requiring itself indirectly and nobody could ever start.
The flavor of the edges decides which algorithms apply. A directed acyclic graph like this one supports a topological sort, an ordering in which every prerequisite comes before the course that needs it, and that guarantee is meaningless on an undirected graph.