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.
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
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 it
- 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.