Algorithms / Graph Modeling State Space
Least You Need to Know: Modeling Interview Problems as Graph Search
Many interview problems become easier once you name the **state** and the **moves**. When states become vertices and legal moves become edges, familiar tools like BFS and DFS suddenly apply.
The least you need to know
- A state-space graph represents each valid situation as a node and each legal move as an edge.
- Many interview graphs are implicit: you generate neighbors on demand instead of storing an explicit adjacency list.
- BFS is the standard choice when every move has equal cost and you want the fewest moves.
- A visited set prevents repeated work and infinite loops in cyclic state spaces.
- Choosing the right state definition is often the hardest modeling step.
Key notation
state
a complete description of one intermediate situation
neighbor
a state reachable in one legal move
implicit graph
a graph whose neighbors are generated when needed rather than listed in advance
Tiny worked example
- In a word-ladder problem, each valid word can be treated as a node.
- Two words share an edge when one allowed transformation changes one into the other.
- Then the fewest transformations question becomes a shortest-path-by-edge-count question.
- That is why BFS is the natural default when each move costs one step.
Common mistakes
- Students often model the input objects as nodes even when the true state needs extra information like position plus remaining budget.
- Students often forget that an implicit graph still needs a visited set if cycles are possible.
- Students often reach for DFS first even when the prompt asks for the fewest moves.
How to recognize this kind of problem
- The prompt asks for the minimum number of moves, edits, hops, or transformations.
- You can describe one legal step from a current situation to a next situation.
- The same state might be reached by multiple different sequences of moves.
Next recommended lesson
Continue through this topic with Least You Need to Know: BFS, DFS, and Connected Components.
Least You Need to Know: BFS, DFS, and Connected ComponentsRelated lessons
Keep going with nearby lessons in the same topic.