cf.completefrontend
GRAPHS · ADVANCED

Bidirectional BFS

Search from the start and from the goal at the same time and stop where the two searches meet, which explores far fewer states.

Time O(b^(d/2))Space O(b^(d/2))2 practice problemsStep-through picture

The idea

A normal BFS spreads out from the start in rings. If each state has 10 next states and the goal is 6 moves away, the last ring can hold about a million states.

Bidirectional BFS runs two searches: one forward from the start and one backward from the goal. Each only needs to go about half the distance before they touch. Two searches of depth 3 visit about 1,000 states each, so about 2,000 in total instead of a million.

It needs two things: you must know the goal state exactly, and moves must work in both directions (if a can move to b, then b can move to a). At each round it grows whichever side is smaller, which keeps the work balanced.

An everyday example

Two friends digging a tunnel from both ends

Two teams dig a tunnel through a hill, one from each side. Each team only digs half the length, and the tunnel is done the moment they break through to each other. If one team's tunnel is getting wide and slow, the other team takes the next turn.

How the example maps to the code
In the exampleIn the code
The team digging from the startThe front set
The team digging from the goalThe back set
Letting the smaller team dig nextSwapping so front is the smaller set
Breaking through to the other tunnelback.has(neighbor)
The total length dugsteps

From the slow way to bidirectional bfs

  1. Start with plain BFS from start. If every state has b moves and the answer is d moves, the last ring can hold about b^d states. With 50 moves per state and an answer of 6, that is over 15 billion states, far too many.
  2. Now look at any shortest path. Its middle state is about d / 2 moves from the start and d / 2 moves from the goal. So a search from the start and a search from the goal, each only half as deep, would both reach that middle. Each touches about b^(d/2) states: with the same numbers, about 125,000 each. The backward search needs moves that can be undone.
  3. The two searches need a way to notice they have met. Keep each side's newest ring as a set, front and back. When the side being grown makes a state that is in the other side's newest ring, a full path exists, and its length is the total number of rounds run by both sides.
  4. The cost of a round grows with the size of the ring being grown. So before each round, swap the names if needed, so front is always the smaller ring. A shared seen set stops either side from walking onto old states. That loop is bidirectional BFS.

How it works

  1. If start equals goal, return 0.
  2. Make front = {start}, back = {goal}, and a shared seen set holding both.
  3. While both sides have states: if front is bigger than back, swap them, so you always grow the smaller side.
  4. Add one to steps and make an empty set next for the new ring.
  5. For each state in front, look at each neighbor. If the neighbor is in back, the searches have met: return steps.
  6. Otherwise, if the neighbor is new, add it to seen and to next.
  7. Set front = next and repeat. If either side runs out of states, 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 bidirectionalSteps(start, goal, neighbors) {
  2. if (start === goal) return 0;
  3. let front = new Set([start]);
  4. let back = new Set([goal]);
  5. const seen = new Set([start, goal]);
  6. let steps = 0;
  7. while (front.size > 0 && back.size > 0) {
  8. if (front.size > back.size) [front, back] = [back, front];
  9. steps++;
  10. const next = new Set();
  11. for (const state of front) {
  12. for (const neighbor of neighbors(state)) {
  13. if (back.has(neighbor)) return steps;
  14. if (seen.has(neighbor)) continue;
  15. seen.add(neighbor);
  16. next.add(neighbor);
  17. }
  18. }
  19. front = next;
  20. }
  21. return -1;
  22. }

How fast it is

TimeO(b^(d/2))
Extra memoryO(b^(d/2))

b is the number of moves per state and d is the answer. Each side only explores about half the depth, and the rings it stores are about that size too.

  • Best caseO(1)

    start === goal returns 0 at once. If the goal is a direct neighbor, the first round finds it after reading one list.

  • Average caseO(b^(d/2))

    Each state has about b moves and the answer is d. Each side explores about half the depth, so it touches about b^(d/2) states.

  • Worst caseO(S · m)

    The graph has few moves per state, like a long chain, or the goal can't be reached from a large start region. Then it does about the same work as plain BFS over S states with m moves each.

Common mistakes

  • Using it when moves can't be reversed. The backward search then finds paths that don't exist.
  • Always growing the same side instead of the smaller one. You lose most of the speedup.
  • Forgetting the start === goal case, which should return 0 before any search.
  • Checking the meeting against the whole other side's history but counting steps as if it were the newest ring. Keep front and back as the newest rings only.

When to use it

Look for these clues in a problem:

  • It's a fewest-moves question with a known start and a known goal.
  • Each state has many possible moves, so plain BFS would explore a huge number of states.
  • Every move can be undone, so the graph can be searched backward from the goal.
  • The answer is a single number of steps, such as the length of a word chain.

Check yourself

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

Why must the code check back.has(neighbor) before seen.has(neighbor)?

The meeting state was added to seen by the other side. Checking seen first would skip it as old, and the two searches would never notice they had met.

Why is the answer steps and not steps + 1 when the sides touch?

steps was already increased at the start of this round, and it counts every round run by both sides. The edge from state to neighbor is the move added in this round.

With 10 moves per state and an answer of 8, about how many states does each approach touch?

Plain BFS can touch about 10^8, which is 100 million. Two searches of depth 4 touch about 2 * 10^4, which is 20,000.

In the trace, why did the start side grow in round 4 without a swap?

front was {3, 4} with 2 states and back was {8, 9, 6} with 3. The swap only happens when front is bigger.

Practice problems

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

Not started

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

Start practicing

medium

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

Say the start side has grown a rounds and the goal side g rounds, so steps is a + g between rounds. Then front and back hold exactly the states that are a moves from the start and g moves from the goal, and seen holds every state within a of the start or within g of the goal. These are the plain BFS facts, kept separately for each side.

A hit is never wrong. When the start side grows state, which is a moves from the start, and its neighbor is in back, which is g moves from the goal, there is a real path of a + 1 + g moves, and that is the new steps. The same holds when the goal side is the one growing, because moves can be undone.

The first hit is never too late either. Take a shortest path of length L, and the round where steps first reaches L. The state a moves along that path is exactly a from the start and L - a from the goal, so only the start side can have it, in its newest ring. The next state on the path is exactly g from the goal and a + 1 from the start, so only the goal side can have it, in back. So the round finds the hit. This is also why back.has must be checked before seen.has: the meeting state is already in seen, added by the other side.

The loop ends because every round adds new states to seen or leaves a side empty. If either side runs out, everything it could reach was explored without touching the other side, so no path exists and -1 is right.

Going deeper

3 more ideas

Why the first meeting gives the shortest answer

Each round adds exactly one step to one side, and steps counts the rounds from both sides together. Before a round, no path of steps moves or fewer exists, or the sides would already have touched. During the round, the new ring touches the other side's latest ring only through a path of exactly steps moves. So the first touch is a shortest path.

How much work it saves

If each state has b moves and the answer is d moves, plain BFS can touch about b^d states. Bidirectional BFS touches about 2 * b^(d/2). With b = 10 and d = 6 that's about 1,000,000 against 2,000.

When it doesn't fit

If moves only work one way, the backward search must use reversed moves, which you may not be able to generate. If the goal is a condition ("any board with the red piece at the exit") rather than one exact state, you can't start a search from it. Use plain BFS or A* in those cases.

Work it by hand

Every step in a table, with why

Fewest edges from 0 to 10 in an undirected graph with 11 nodes, where neighbors(x) returns graph[x].

graph = [[1, 2], [0, 3], [0, 3, 4], [1, 2, 5], [2, 6], [3, 7], [4, 7, 10], [5, 6, 8, 9], [7, 10], [7, 10], [8, 9, 6]], start = 0, goal = 10

StepstepsSide grownstateNeighborsnext afterbackWhy
10----{10}front = {0}, back = {10}, and seen holds both. Both rings have 1 state, so there is no swap.
21start01 new, 2 new{1, 2}{10}Neither 1 nor 2 is in back, so both join the new ring. front becomes {1, 2}.
32goal108 new, 9 new, 6 new{8, 9, 6}{1, 2}front (2 states) is bigger than back (1 state), so they swap. Now the goal side grows.
43start10 seen, 3 new{3}{8, 9, 6}The goal side's ring {8, 9, 6} is now bigger than {1, 2}, so they swap back and the start side grows.
53start20 seen, 3 seen, 4 new{3, 4}{8, 9, 6}3 was added a moment ago from 1, so the shared seen set skips it.
64start31 seen, 2 seen, 5 new{5}{8, 9, 6}{3, 4} has 2 states and back has 3, so there is no swap: the start side grows again.
74start42 seen, 6 is in back-{8, 9, 6}6 is in the goal side's newest ring. The two searches touch, so return steps = 4.

It returns 4, the path 0 → 2 → 4 → 6 → 10. Node 7 was never touched. On a graph this small there is no saving: plain BFS from 0 puts 8 states in seen here, and this run put 10. The saving shows when each state has many moves.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bidirectional BFSO(√n)O(√n)Here n is the number of states plain BFS would touch. With one known goal, moves that can be undone, and even branching, two half-depth searches touch about 2√n states.
BFS on an implicit graphO(n)O(n)The goal is a condition rather than one state, moves can't be undone, or the search space is small enough already.
A* searchO(n log n)O(n)You have a good estimate of the remaining distance, so the search can lean toward the goal instead of spreading out.

Extra memory: O(b^(d/2)) in the typical case for seen and the two rings; in the worst case, every reached state is in seen.

How the steps grow

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

Inputs that need care

5 tricky inputs
start === goal
Return 0 before making any sets. Without that line, front and back both hold the same state, and the search only stops when some path loops back to it, returning a positive number instead of 0.
The goal is a direct neighbor of the start
Round 1 grows the start side, finds the goal in back, and returns 1.
The goal sits in a small piece that the start can't reach
The goal side is the smaller ring, so it keeps growing until it runs out, then the loop stops with -1. In a test with a 40-node tree around the start and a 3-node piece around the goal, it touched 6 states, while plain BFS touched all 40.
One-way moves, such as a directed graph
The goal side would walk edges in the wrong direction and find paths that don't exist. Give the backward search a reversed neighbors function, or use plain BFS.
The goal is a condition, such as "any board with the red piece at the exit"
There is no single state to start the backward search from. If you can list every goal state, put all of them in back at the start; otherwise use plain BFS or A*.

Variations and follow-ups

Twists interviewers add

Returning the path

Keep a parent map for each side. When the sides touch, walk the start side's map back from state and the goal side's map back from neighbor, then join the two halves.

Strict turns instead of smaller-first

Some versions just alternate sides every round. That is simpler but loses the balance: if one side branches much more, it does most of the work.

Bidirectional Dijkstra

With edge costs, run two heaps. The stopping rule is harder: the first meeting may not be the cheapest, so keep the best total seen and stop when the two heap tops together cost at least that much.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a fewest-moves question with a known start and a known goal and a huge number of moves per state, such as changing one letter at a time through a large dictionary.
  • Explain the saving with numbers: "with 10 moves per state and an answer of 6, plain BFS can touch a million states; two searches of depth 3 touch about 2,000".
  • Test by hand: start equal to goal, goal one move away, and a goal that can't be reached. The last one checks that the loop stops when either side is empty.
  • Expect "why grow the smaller side?". Answer: a round costs about the size of the ring being grown, so growing the smaller one keeps both sides cheap. Also expect "what if moves are one-way?": then it needs reversed moves for the goal side.

Where frontend code uses it

The same idea in real UI code
  • Finding the degree of connection between two users in a large social graph, such as "you are 3 steps from this person".
  • Word-chain games and puzzles in the browser that need the shortest solution quickly, even with large dictionaries.
  • Route finding between two known pages in a large site map, where both the start and the goal are fixed.

Related algorithms