cf.completefrontend
GRAPHS · CORE

BFS on an implicit graph

Find the fewest moves between two states when the graph is never written down, only a rule for which moves are allowed.

Time O(S * m)Space O(S)5 practice problemsStep-through picture

The idea

Many puzzles are graphs even though nobody gives you a list of edges. The nodes are states, such as a lock showing "0000", a number on a screen, or a puzzle board. The edges are the allowed moves, such as turning one wheel of the lock. This is called an implicit graph: it exists only as a rule.

You can't build the whole graph first, because it may have millions of states, most of which you will never need. Instead you write a neighbors(state) function that creates the next states on demand, and run BFS with it.

BFS still gives the fewest moves, because each move counts as one step. The only new parts are that states are often strings or numbers instead of indexes, so you remember them in a Set, and you stop as soon as you reach the goal.

An everyday example

Solving a combination lock by trying moves

You know the starting combination and the one that opens the lock, and one move turns a single wheel by one notch. Nobody hands you a map of all 10,000 combinations. You first list every combination one move away, then every combination two moves away, and so on, crossing off ones you've already listed. The first time the opening combination shows up, the number of rounds is the fewest moves.

How the example maps to the code
In the exampleIn the code
A combination on the lockA state
Turning one wheel by one notchOne result of neighbors(state)
Combinations you've already listedThe seen set
Everything one more move awaynextFrontier
The number of rounds so farsteps

From the slow way to bfs on an implicit graph

  1. The obvious plan: list every possible state, build the full adjacency list, then run BFS. That's fine for a 4-wheel lock with 10,000 states. A 4 by 4 sliding puzzle has about 10 trillion reachable boards, and you can't even store the list of nodes, let alone the edges.
  2. Look at what BFS actually asks the graph. It only ever needs one thing: "what are the neighbors of this state?", and only for states it has reached. It never needs the whole graph at once.
  3. So replace graph[node] with a function, neighbors(state), that makes the next states when they are asked for. States are now strings or numbers instead of indexes, so the dist array becomes a Set called seen, which remembers every state already reached.
  4. Instead of storing a distance for each state, handle the search in rounds. frontier holds the states found in the last round, steps counts rounds, and the search stops the first time goal is made. That loop is BFS on an implicit graph.

How it works

  1. If start already equals goal, return 0.
  2. Put start in seen and in the first frontier, and set steps to 0.
  3. While the frontier has states, add one to steps and start an empty nextFrontier.
  4. For each state in the frontier, create its moves with neighbors(state).
  5. If a move reaches goal, return steps. If it was seen before, skip it. Otherwise add it to seen and to nextFrontier.
  6. Replace frontier with nextFrontier and repeat. If the frontier runs out, the goal can't be reached: return -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function shortestSteps(start, goal, neighbors) {
  2. if (start === goal) return 0;
  3. const seen = new Set([start]);
  4. let frontier = [start];
  5. let steps = 0;
  6. while (frontier.length > 0) {
  7. steps++;
  8. const nextFrontier = [];
  9. for (const state of frontier) {
  10. for (const next of neighbors(state)) {
  11. if (next === goal) return steps;
  12. if (seen.has(next)) continue;
  13. seen.add(next);
  14. nextFrontier.push(next);
  15. }
  16. }
  17. frontier = nextFrontier;
  18. }
  19. return -1;
  20. }

How fast it is

TimeO(S * m)
Extra memoryO(S)

S is the number of states reached and m is the number of moves from each. Every reached state is stored once in seen.

  • Best caseO(1)

    start === goal, so it returns 0 before searching. Next best, the goal is one of the start's own moves.

  • Average caseO(S · m)

    S is the number of states reached before the goal shows up and m is the moves per state. Each reached state is expanded once.

  • Worst caseO(S · m)

    The goal can't be reached, so every reachable state is found and expanded before the frontier runs out.

Common mistakes

  • Trying to build the full graph up front. Generate moves only when a state is taken from the frontier.
  • Using arrays as states and putting them in a Set. Two equal arrays are different objects, so seen.has never matches. Turn states into strings like board.join(",").
  • Letting states grow without a limit, so BFS runs forever on an unreachable goal.
  • Forgetting forbidden states, or forgetting that the start itself might be forbidden.

When to use it

Look for these clues in a problem:

  • The question asks for the fewest moves, presses, swaps, or changes to turn one thing into another.
  • The input describes a start, a goal, and rules for a single move, not a list of edges.
  • States are strings, board layouts, or numbers, and the number of possible states is large but limited.
  • Some states are forbidden, such as dead ends or walls.

Check yourself

Answer each one in your head first, then open it.

Why does the code check next === goal before checking seen?

The goal is never in seen, so either order would work here. Checking it first just returns as soon as it is made, without storing it or finishing the round.

How many states were in seen when the trace returned?

12: 2, 6, 1, 18, 5, 3, 0, 17, 15, 4, 9, 16. The goal itself was never added.

What happens to an unreachable goal if states have no upper limit?

The frontier never empties, because tripling keeps making new, bigger states. The loop runs until it runs out of memory or time.

Why count rounds with steps instead of storing a distance for each state?

Every state in one round is the same number of moves away, so one counter is enough. It saves a map entry per state and keeps the code short.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Just before a round adds 1 to steps, two facts hold. frontier holds exactly the states whose fewest number of moves from start is steps, and seen holds exactly the states that are steps moves away or fewer. Before the first round, steps is 0 and both hold only start.

A round keeps both facts. After the increment, every state made from the frontier is at most steps moves away. If it isn't in seen, it isn't closer than that, so it is exactly steps moves away, and it goes into nextFrontier. Every state that is exactly steps moves away has a neighbor one move closer, which is in the frontier, so the round finds all of them.

The goal is never added to seen, because the goal check comes first. So the first time it is made is in the round equal to its distance, and returning steps there is correct. The loop ends because each round either adds new states to a limited set of states or leaves nextFrontier empty. An empty frontier means every reachable state was found and none was the goal, so -1 is right.

Going deeper

3 more ideas

Why handling a whole frontier at a time is helpful

The frontier holds exactly the states that are steps - 1 moves from the start. Every state in nextFrontier is steps moves away. Handling the frontier as a group lets you count moves with one variable, steps, instead of storing a distance for every state.

Keep the state space limited

If moves can grow forever (like doubling a number), BFS might explore states that can never help. Add a sensible limit in neighbors, such as "never go above twice the goal". Also make sure forbidden states are never added: check them in neighbors or put them into seen at the start.

How the cost grows

The time is about the number of states you visit times the number of moves from each. A 4-wheel lock has 10^4 = 10,000 states and 8 moves from each, about 80,000 checks. A puzzle with 20 pieces could have far more states than BFS can visit, which is when bidirectional BFS or A* becomes useful.

Work it by hand

Every step in a table, with why

Fewest moves from 2 to 14, where one move is "times 3" or "minus 1", and states must stay between 0 and 28.

start = 2, goal = 14, neighbors = (x) => [x * 3, x - 1].filter((y) => y >= 0 && y <= 28)

StepstepsstateMoves madenextFrontier afterWhat happensWhy
1126 new, 1 new[6, 1]Round 1From 2, times 3 gives 6 and minus 1 gives 1. Neither is the goal, so both are remembered.
22618 new, 5 new[18, 5]Round 2 beginsfrontier is now [6, 1], every state 1 move from the start.
3213 new, 0 new[18, 5, 3, 0]Round 2 endsFour states are exactly 2 moves away.
431817 new[17]54 is out of rangeTimes 3 gives 54, above 28, so neighbors drops it. Only 17 is made.
53515 new, 4 new[17, 15, 4]Two new states15 will turn out to be one move from the goal.
6339 new, 2 seen[17, 15, 4, 9]Skip the startMinus 1 leads back to 2, which is in seen, so it is skipped.
7300 seen[17, 15, 4, 9]Nothing newTimes 3 of 0 is 0 again, and minus 1 gives -1, which is dropped.
841716 new[16]Round 451 is dropped, and 16 is new.
941514 is the goal-Return 4Times 3 gives 45, dropped. Minus 1 gives 14, the goal, so the answer is the current round number.

It returns 4: 2 → 6 → 5 → 15 → 14. Only 12 states went into seen, and the search stopped in the middle of round 4 without handling 4, 9, or 16.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
BFS on an implicit graphO(S · m)O(S)You need the fewest moves, the states are made by a rule, and only part of the state space will be reached.
Build the full graph, then BFSO(S · m)O(S · m)The whole state space is small and you will run many searches on it, so building it once pays off.
Bidirectional BFSO(√S)O(√S)The goal is a single known state and moves can be undone. When every state branches evenly, two half-depth searches touch about the square root of what one full search touches.
A* searchO(S log S)O(S)You have a good estimate of the moves left from any state, which lets the search head toward the goal instead of spreading evenly.

Extra memory: O(S): seen holds every reached state, and the two frontiers together hold at most that many.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for BFS on an implicit graph and the other approaches, on a scale where each line up is 10 times more steps.
  • BFS on an implicit graph, Build the full graph, then BFS O(S · m)
  • Bidirectional BFS O(√S)
  • A* search O(S log S)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
BFS on an implicit graph1001 million1 trillion
Build the full graph, then BFS1001 million1 trillion
Bidirectional BFS3321,000
A* search339,96620 million

Inputs that need care

5 tricky inputs
start === goal
Return 0 right away. Without that line the search would only notice the goal when some sequence of moves led back to it, so it would return a positive number, or -1 if no moves ever lead back.
The goal can't be reached: start = 0, goal = 5 with the trace's moves
Times 3 of 0 is 0, already seen, and -1 is dropped. The first round makes nothing new, the frontier empties, and the result is -1.
No limit on the states
Without the 0 to 28 range, tripling grows forever and an unreachable goal never returns. Every limit must be one you can show never cuts off a shortest answer.
Forbidden states, such as dead-end lock codes
Put them in seen before the search so they are never entered. Check the start first: if it is forbidden, the answer is -1 without searching.
States that are arrays, such as a board [1, 0, 2]
Two equal arrays are different objects, so seen.has never matches. Turn each state into a string key, such as board.join(",").

Variations and follow-ups

Twists interviewers add

Returning the moves

Keep a Map from each new state to the state it came from. When the goal is found, follow that map back to the start and reverse it to list every move.

Bidirectional BFS

When the goal is one exact state and every move can be undone, search from both ends and stop when they meet. Each side only goes about half as deep, which can save a huge number of states.

Faster neighbor generation

Sometimes making the moves is the slow part, such as comparing a word against a whole dictionary. Group allowed states by a pattern, like a word with one letter blanked out, so the neighbors can be looked up instead of searched for.

Moves with costs

If different moves cost different amounts, BFS rounds no longer match cost. Run Dijkstra's algorithm over the same neighbors function with a heap instead.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "minimum number of moves, operations, or changes to turn X into Y" when there is no edge list, only rules for one move.
  • Before coding, say what a state is, what neighbors(state) returns, and how you turn a state into a key for seen. Those three choices are the whole design.
  • Test by hand: start equal to goal, a goal that can't be reached, and a forbidden start. Each one has a special return value.
  • Expect "can you make it faster?". Answer: search from both ends with bidirectional BFS, or use A* with a good estimate. Also expect "how many states could there be?", and give a number, like 10^4 for a 4-wheel lock.

Where frontend code uses it

The same idea in real UI code
  • Puzzle and game UIs (sliding tiles, lock dials) that show the fewest moves or offer a hint for the next move.
  • Editors that find the fewest single-character edits between names in a list of allowed names, used for "did you mean" suggestions.
  • Layout tools that search for the fewest moves to reorder cards or panels into a target arrangement.

Related algorithms