Graph problems rarely say "graph"
Interviews and real systems hand you stories, not adjacency lists. The skill is translation. Ask three questions:
- 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" → shortest path (BFS, lesson 5-3). "Can I reach X?" → connectivity. "Valid order to do these?" → topological sort (Algorithms course).
Example: "What is the fewest flights from SFO to JFK?" Nodes = airports, edges = direct routes, question = shortest path in hops. Because BFS explores ring by ring, the ring where JFK first appears IS the answer.
Even a maze is a graph: every open square is a node, edges connect touching squares. No pointers in sight, still a graph.
Code exercise · python
Your turn: implement `shortest_hops(adj, start, goal)` with BFS. Keep a `dist` dict mapping each reached node to its hop count (it doubles as the `seen` set from lesson 5-3). Return the goal's distance when you pop it, or -1 if the frontier empties first.
Quiz
"Given a dictionary of words, can you turn 'cold' into 'warm' changing one letter at a time, every step being a real word?" What are the nodes and edges?
Quiz
Why did `shortest_hops` need the `dist` dict to double as a seen-check (`if neighbor not in dist`)?
Problem
A course catalog says: to take Algorithms you need Data Structures, and to take Data Structures you need Advanced Python. As a graph, what are the edges: "prerequisite arrows" or "friendship pairs"? Answer with directed or undirected.