Lesson 21.3 · Breadth-First Search
Implicit Graphs: States as Nodes
Often the graph isn't given. Each state (a word, a lock combination, a board) is a node, and each legal move is an edge, generated on the fly.
10 min
Think of it like this
Solving a Rubik's cube by trying every single twist from the current position: the positions are nodes, twists are edges, and nobody ever draws the whole graph.
1.Generate neighbours, don't store them
Define a state, a start state, a goal test, and a function listing the states one move away. Store visited states in a HashSet. BFS then finds the fewest moves.
Example: a 4-digit lock where each move turns one wheel up or down has 10⁴ states and 8 moves per state. Word Ladder's neighbours are words that differ in one letter: try 26 letters at each position instead of comparing against every word.
When both start and goal are known, bidirectional BFS grows from both ends and stops when they meet, exploring far fewer states.
Quick check
How many neighbours does a 4-wheel lock state have?
Remember
- State = node, move = edge.
- HashSet of visited states.
- Bidirectional BFS for known start and goal.
Common mistakes
- Building the full graph up front (often huge).
- Forgetting to treat forbidden states as visited.