“hit” becomes “cog” through a chain of single-letter changes: hit, hot, dot, dog, cog. Each word is a real dictionary word. Each step changes exactly one letter. The question: what is the shortest such chain?

This looks like a word puzzle. But there is a graph hiding in plain sight. Every word in the dictionary is a node. Every pair of words that differ by exactly one letter is connected by an edge. The Word Ladder problem (LC 127) is asking: what is the shortest path from “hit” to “cog” in this graph?

Once you see the graph, the algorithm writes itself. Shortest path on unweighted edges means BFS. But this graph is unusual -- nobody hands you an adjacency list. There is no graph["hit"] = ["hot", "hat", "bit", ...] sitting in memory. The edges are implicit: you discover them by generating every possible single-letter substitution and checking which ones are valid dictionary words. The graph exists in theory, and BFS explores it lazily, generating neighbors on the fly.

This is the pattern of implicit graphs -- and it unlocks a massive class of problems that do not look like graph problems at all.

Here are seven three-letter words. Some of them differ by exactly one letter. Your job: figure out which pairs are connected before the graph reveals itself.

Think about it concretely. “hot” and “dot” differ by one letter (h versus d). That is an edge. “hot” and “dog” differ by two letters. No edge. The rule is mechanical: compare character by character, count the differences, connect if the count is exactly one.

That one-letter difference is an edge. Each word is a node. The graph has been there the whole time -- you just could not see it because nobody drew it for you. This is the defining feature of implicit graphs: the structure exists in the rules of the problem, not in a data structure handed to you as input.

Once the graph reveals itself, notice its shape. Some words are hubs with many connections (words with common patterns). Others are dead ends with only one or two neighbors. BFS on this graph naturally finds the shortest transformation sequence, just like BFS on any unweighted graph finds the shortest path.

Word Ladder has no graph[node]. There is no adjacency list sitting in memory. The graph is too large to precompute -- a dictionary with 5,000 words could have millions of edges. Instead, neighbors are generated on the fly by trying every single-letter substitution and checking whether the result exists in the dictionary.

This is the key insight of implicit graphs: you do not need the graph to exist in memory. You only need a function that, given a node, returns its neighbors. BFS does not care whether neighbors come from an adjacency list, a matrix lookup, or a computation. It just needs getNeighbors(node) to return the right set.

The neighbor function is the contract. For Word Ladder, it generates 26 * wordLength candidates and filters by dictionary membership. For a grid, it checks the 4 (or 8) adjacent cells. For a combination lock, it tries incrementing and decrementing each dial. Different problems, different neighbor functions, same BFS skeleton.

This reframing -- “if I can define neighbors, I can BFS it” -- is what turns problems like Open the Lock, Minimum Knight Moves, Sliding Puzzle, and Escape a Large Maze into graph problems. None of them come with an adjacency list. All of them have a well-defined neighbor function. And all of them are shortest-path problems on implicit, unweighted graphs.

A 4-digit combination lock starts at 0000. Each move turns one dial by +1 or -1 (wrapping: 9+1=0, 0-1=9). Some combinations are deadends -- if you land on one, the lock jams and you cannot continue. Find the minimum number of moves to reach the target combination.

This is Open the Lock (LC 752), and it is a perfect implicit graph problem. Every 4-digit combination is a node (10,000 total). Every dial turn is an edge -- each state has exactly 8 neighbors (4 dials times 2 directions). The deadends are “walls” that BFS cannot pass through, similar to blocked cells in a grid.

The state space is large (10,000 nodes) but BFS does not need to explore all of it. It expands from “0000” level by level and stops the moment it reaches the target. The wavefront might touch only a fraction of the 10,000 states -- especially when deadends block large regions of the state space.

Try to reach the target yourself by turning dials. Notice how many moves you need. Then see how BFS would do it -- the minimum path might be shorter than you expect.

The neighbor function is the one piece of BFS that changes from problem to problem, and getting it wrong means BFS explores a completely different graph -- silently producing wrong answers.

On a grid, “neighbors” depends entirely on the movement rules. A flood fill uses 4 directions (up, right, down, left). A shortest-path-in-matrix problem might allow 8 directions (adding diagonals). A knight on a chessboard has 8 L-shaped moves, none of which overlap with the grid's natural adjacency.

The neighbor function defines the graph. If you use 4-directional movement on a problem that allows diagonals, BFS will report paths as longer than they actually are -- or report “no path” when a diagonal shortcut exists. If you use 8-directional movement on a problem that only allows cardinal directions, BFS will find shortcuts that are not legal moves.

This is why reading the problem statement carefully matters so much for implicit graph problems. The movement rules are the graph definition. Every other part of BFS -- the queue, the visited set, the distance tracking -- stays the same. The neighbor function is the only variable.

Explore the direction patterns below. Notice how each movement rule produces a dramatically different BFS tree from the same starting cell.

You are solving Minimum Knight Moves on an 8x8 board. A knight moves in an L-shape: two squares in one direction, one square perpendicular. This gives 8 possible moves from any position (fewer near edges).

This is the exercise that separates “understanding implicit graphs conceptually” from “being able to implement them.” The BFS skeleton you have been writing all along -- queue, visited set, distance tracking -- is completely generic. It does not know what kind of graph it is exploring. The only piece that encodes the problem is the neighbor function, and for grid-based implicit graphs, the neighbor function is defined entirely by a directions array. Get the directions right, and BFS solves the problem. Get them wrong, and BFS solves a different problem -- silently, with no error, producing a plausible-looking but incorrect answer.

The challenge: select the correct direction offsets from a set of candidates. Some offsets represent valid knight moves. Others represent bishop moves, rook moves, or other chess pieces. BFS will faithfully explore whatever graph your offsets define -- if you pick wrong, it computes the shortest path for a different piece entirely. This is not hypothetical: confusing knight offsets with king offsets is one of the most common bugs in chess-based BFS problems, because both produce answers that look reasonable on small boards.

This exercise isolates the critical skill for implicit graph problems: translating the problem's movement rules into a concrete directions array. For Word Ladder, the “directions” are 26 letter substitutions per position. For Open the Lock, they are +1 and -1 on each of 4 dials. For a knight, they are the 8 L-shaped offsets. The translation from English description to coordinate offsets is where most bugs hide.

Select the correct direction offsets, then run BFS with your choices. Watch the resulting path -- does it look like a knight's movement, or something else?

When the state space is huge, standard BFS can explore an enormous number of nodes before reaching the target. If the shortest path has length d and the branching factor is b, BFS explores roughly b^d states. On Open the Lock with a branching factor of 8 and a path length of 6, that is 8^6 = 262,144 states.

Bidirectional BFS cuts this dramatically by running two searches simultaneously -- one from the start, one from the target -- and stopping when the wavefronts meet. Each search only goes d/2 deep, exploring roughly b^(d/2) states. For our example: 2 * 8^3 = 1,024 states instead of 262,144. The savings come from the exponential: halving the depth squares the speedup.

The algorithm alternates between expanding the start frontier and the end frontier (always expanding the smaller one for optimal performance). At each step, it checks whether the newly discovered nodes overlap with the other frontier's visited set. The moment any node appears in both visited sets, the two searches have met in the middle, and the total shortest path is the sum of the two half-distances.

Bidirectional BFS works only when you know both the start and the target state, and when the graph is undirected (or you can reverse the edges). It does not apply to problems like “find the nearest X” where the target is unknown.

Watch the two wavefronts converge below. Notice how much less of the state space is explored compared to unidirectional BFS.

Not every BFS problem has an implicit graph. Binary tree level-order traversal? The tree is handed to you -- explicit. Shortest path in an adjacency-list graph? Also explicit. Word Ladder? No graph given -- you generate neighbors from the dictionary. That is implicit.

The tell: do you need to generate neighbors, or are they given to you? If the problem gives you nodes and edges (adjacency list, adjacency matrix, tree pointers), the graph is explicit. If the problem gives you rules (movement constraints, transformation rules, state transitions) and you must compute neighbors from those rules, the graph is implicit.

Implicit graphs are often enormous. Open the Lock has 10,000 states. Sliding Puzzle (LC 773) has 720 states. A 4x4 grid with 8-directional movement has 16 nodes but could be part of a larger state-space graph if you add conditions. The good news: BFS does not need the full graph in memory. It generates neighbors lazily, one level at a time, and stops as soon as it finds the target.

For each problem below, decide: is the graph implicit (neighbors generated from rules) or explicit (neighbors given in the input)?

Word Ladder, Open the Lock, Minimum Knight Moves, Sliding Puzzle -- they all use the same BFS template. The structure is identical every time: initialize a queue with the start state, mark it visited, then loop (dequeue, generate neighbors, enqueue unvisited neighbors with distance+1, stop when target is found).

This is the culminating insight of the implicit graphs lesson: the BFS skeleton is a universal solver for shortest-path problems on unweighted graphs. You have now seen it applied to word transformations, combination locks, chess pieces, and grid traversals. In every case, the queue management, visited tracking, and distance bookkeeping were identical. The only variable was the neighbor function -- one function that encodes the entire problem domain.

The practical consequence is that when you encounter a new problem that asks for “minimum number of moves” or “shortest transformation sequence,” your workflow becomes: (1) identify what a “state” is, (2) identify what a “move” is (these are the edges), (3) write getNeighbors(state), (4) paste the BFS skeleton. Steps 1-3 require understanding the problem. Step 4 is mechanical. This decomposition is what makes implicit graph problems tractable under time pressure -- you spend your thinking time on the neighbor function, not on reinventing BFS.

Fill in the three blanks: neighbor generation (the problem-specific part), visited check (the correctness guarantee), and state tracking (the distance counter). Once you can write this skeleton without thinking, every implicit graph problem reduces to defining one function.

Three questions on the core ideas of implicit graphs.

This lesson introduced a way of seeing that extends far beyond BFS. The implicit graph mental model -- “if I can define states and transitions, I have a graph” -- applies to problems that never mention the word “graph” in their description. Sliding Puzzle (LC 773) talks about tile arrangements. Open the Lock (LC 752) talks about combination dials. Minimum Genetic Mutation (LC 433) talks about DNA strings. None of them look like graph problems on the surface. All of them are shortest-path problems on implicit, unweighted graphs once you identify the state and the transitions.

The power of this reframing is that it lets you reuse everything you already know about BFS. Shortest paths? Guaranteed by the FIFO queue. Correctness? Guaranteed by the distance invariant. Efficiency? Guaranteed by mark-on-push. You do not need to invent a new algorithm for each new problem domain -- you need to define one function (getNeighbors) and paste the skeleton. The hard part is the recognition, not the implementation.

The first question tests whether you can identify an implicit graph in a problem that does not obviously look like a graph problem. The second asks about the relationship between the neighbor function and the graph structure -- what happens when you define neighbors incorrectly? The third tests bidirectional BFS: when does it apply, and why does halving the search depth produce such dramatic savings?