State-space & Implicit Graph BFS

The Senior+ recognition skill

Graph Representation & Traversal taught you BFS/DFS when the graph is given — adjacency lists, grids, explicit edges. This subtopic is the next gear: the problem never says "graph," never hands you an adjacency list, and the vertices are not physical nodes at all. You invent the vertex set. Each vertex is a state that fully describes "where I am" in the search (a password string, a bus currently riding, a bitmask of keys collected plus a cell). Neighbors are the legal one-step transitions from that state. Once that model is right, the algorithm collapses to ordinary BFS for fewest moves — the same queue and visited set you already trust.

This is the pattern that gates hard Senior loops more often than Floyd-Warshall. Word Ladder is the canonical warm-up; Open the Lock, Bus Routes, and Shortest Path to Get All Keys are the same idea with larger or richer states.

What counts as a "state"

A state is any tuple of information such that:

1. Two configurations with the same tuple are interchangeable for the rest of the search — no hidden progress lives outside the tuple.
2. One legal move produces another state — the edge set is defined by the move rules, not by an input graph.
3. The start and goal are specific states (or sets of states) you can enqueue and recognize.

Problem shape	State	Neighbors
Transform word A → word B, one letter at a time, staying in a dictionary	current word (string)	all dictionary words that differ by one character
Open a 4-dial lock, avoid deadends	4-digit string	±1 on each dial (8 neighbors), skipping deadends
Ride buses to a target stop	(current_stop, …) or often just the stop, with edges = "all stops on any bus that serves here"	careful: modeling buses vs stops changes complexity
Collect all keys on a grid	(row, col, key_bitmask)	4-directional moves; picking up a key flips a bit; doors need the matching bit

The interview skill is stating the state out loud before coding: "My node is (position, keys_held). Visited must key on the full triple, not just the cell — otherwise I refuse a later visit to the same cell with more keys."

Implicit edges: generate, don't build

You almost never materialize the full adjacency list. At each dequeued state, generate neighbors on the fly:

Mark visited when you enqueue, exactly as in ordinary BFS — otherwise the same state floods the queue from many parents.

Visited must cover the whole state

The #1 Senior bug: visiting a component of the state and discarding the rest.

• Grid + keys: visiting (r, c) alone is wrong — you may need to re-enter (r, c) after picking up a new key.
• Bus routes: if your state is only the stop, that is fine only if edges already encode "take any bus from here." If your state is (stop, bus_id), visited must include both.

Rule: if two walks can reach the same partial configuration with different remaining options, those are different vertices.

Bidirectional BFS

When the branching factor is high and both start and goal are known, run BFS from both ends and stop when the frontiers meet. Each side expands roughly half the depth, so a tree of branching factor b and depth d drops from ~b^d to ~2 · b^(d/2) — often a large practical win on Word Ladder–style graphs.

Say this tradeoff out loud: bidirectional BFS needs a clear goal state and an invertible (or at least generable-backward) neighbor relation. It does not help when the goal is "any state satisfying a predicate you cannot invert," or when edges are weighted (then you need Dijkstra / 0-1 BFS on the same state graph).

When the state graph is weighted

Unit-cost moves → BFS (this subtopic). Non-negative varying costs on transitions → Dijkstra on the same state space (Shortest Paths). Only 0/1 transition costs → 0-1 BFS. Constrained "at most k stops" is again a state expansion: (node, stops_used) with BFS or Dijkstra depending on weights — you already saw that row in the Shortest Paths decision table; the modeling lesson lives here.

Complexity, precisely

Time and space are O(|S| · T) where |S| is the number of distinct reachable states and T is the cost to enumerate neighbors of one state. For Open the Lock, |S| ≤ 10^4 and T = 8. For key-collection grids, |S| ≤ R · C · 2^K — if K is up to 6, that is fine; if K is 20, the state space is the wrong approach (or needs meet-in-the-middle / another structure). Always bound |S| from the constraints before coding; interviewers listen for that estimate.

Pitfalls and interview gotchas

• Building the explicit graph first. For Word Ladder, precomputing all pairs is O(n² · L); better generate neighbors via a wildcard pattern map ("*ot" → [hot, dot, lot]) in O(n · L²), then BFS. Same spirit: generate smart, don't materialize every edge blindly.
• Forgetting deadends / blocked states at the start. If start itself is forbidden, return failure immediately — do not only filter neighbors.
• Treating DFS as interchangeable with BFS for fewest moves. On an unweighted state graph, only BFS (or bidirectional BFS, or 0-1 BFS) gives shortest length; DFS finds a path.
• Huge neighbor generation inside the hot loop without caching. Bus Routes: iterating every bus at every stop repeatedly is too slow — index stop → list of bus ids once, and mark buses (or stops) visited so you do not re-expand the same bus.
• Bidirectional BFS with asymmetric neighbors. If forward and backward moves differ (one-way edges), you must generate predecessors on the backward search, not re-use the forward neighbor function.

Where this sits on the roadmap

• Before: Graph Representation & Traversal — queue discipline, mark-on-enqueue, multi-source BFS. Grids are the special case where state = (r, c).
• After: Shortest Paths — same state idea with a heap when edges have weights; Topological Sort when the "moves" are dependencies rather than steps.
• Related: Backtracking also walks an implicit state tree, but it explores all solutions (or searches with pruning). Here you only need the shortest path in an unweighted state graph — BFS, not the backtracking stack.