A single breadth-first search grows one expanding ball of explored nodes until it swallows the goal — and that ball’s size explodes with distance. Bidirectional BFS runs two searches at once: one forward from the start, one backward from the goal, each stopping when its frontier touches the other’s. Two small balls that meet in the middle explore dramatically fewer nodes than one big ball — turning roughly b^d into 2·b^(d/2). Step the two frontiers and watch them collide.
explores ~2·b^(d/2) vs b^d nodes · needs a known goal & reversible edges
forward frontier
The BFS wave growing outward from the start.
backward frontier
The BFS wave growing outward from the goal (over reversed edges).
meeting
When a node is reached by both searches — the frontiers have touched.
shortest path
Stitch the forward path to the meeting node with the backward path from it.
bidi.js — two frontiers, one meeting point
Ready
A grid with a start (left) and goal (right). One BFS grows from each. Step expands both frontiers by one layer; they stop the instant they touch.
2
bidi explored
–
1-way BFS
0
layers
How it works
The saving is exponential, and it comes straight from the geometry. A one-way BFS to a goal at distance d explores on the order of b^d nodes (branching factor b). Split the job in half and each search only has to reach distance d/2 before they meet — exploring about b^(d/2) nodes each, or 2·b^(d/2) total. Because the exponent is halved, even a modest distance turns a huge search into a small one.
1
Two frontiers, alternating
Keep a BFS frontier from the start and another from the goal. Each step, expand both by one layer, marking newly-reached cells for each side.
2
Watch for a touch
After expanding, check whether any cell is now reached by both sides. The first such cell is where the two shortest half-paths join.
3
Stitch the path
Follow parent pointers from the meeting cell back to the start (forward search) and forward to the goal (backward search), then join the two halves.
✓
When it applies
You need a known goal (so you can search backward from it) and edges you can traverse in reverse. Given both, bidirectional BFS finds the same shortest path as BFS while exploring far fewer nodes.
One-way BFS
~b^d
Bidirectional
~2·b^(d/2)
Finds
shortest path
Needs
known goal
The code
# expand the smaller frontier each round; stop when they meetdef bidirectional_bfs(adj, start, goal):
if start == goal: return [start]
fwd = {start: None}; bwd = {goal: None} # node -> parent
front, back = {start}, {goal}
while front and back:
if len(front) > len(back): front, back, fwd, bwd = back, front, bwd, fwd
nxt = set()
for u in front:
for v in adj[u]:
if v in bwd: return stitch(fwd, bwd, u, v) # frontiers touchedif v notin fwd: fwd[v] = u; nxt.add(v)
front = nxt
Quick check
1. Why does bidirectional BFS explore far fewer nodes than one-way BFS?
One-way BFS grows a ball of radius d (~b^d nodes). Two searches each grow to radius d/2 before touching (~b^(d/2) each). Halving the exponent is an exponential reduction — the core win.
2. What does bidirectional BFS require that plain BFS does not?
You must know the goal (to start the backward search there) and be able to traverse edges in reverse. Plain BFS only needs a start. If the goal is unknown or edges are one-way with no reverse, bidirectional BFS does not apply.
3. How is the shortest path recovered when the frontiers meet?
Each search keeps parent pointers. From the meeting cell, walk forward-parents back to the start and backward-parents forward to the goal, then concatenate the two half-paths.
FAQ
What is bidirectional BFS?
A shortest-path search running two breadth-first searches at once — forward from the start, backward from the goal — stopping when their frontiers meet. Each search reaches only half the distance, so it explores ~2·b^(d/2) nodes instead of b^d.
When can you use bidirectional BFS?
When you have a single known goal (to search backward from) and reversible edges, on unweighted graphs where BFS gives shortest paths. It doesn’t apply with an unknown goal, many goals, or non-reversible edges.
How much faster is it than one-way BFS?
Explored nodes drop from ~b^d to ~2·b^(d/2). Halving the exponent is exponential — e.g. b=10, d=6 is ~1,000,000 nodes one-way versus ~2,000 bidirectional.
How does it compare to A* search?
Bidirectional BFS shrinks the search from both ends; A* shrinks it with a heuristic steering toward the goal. They’re complementary (bidirectional A* combines them). BFS-both-ends needs no heuristic but needs a known goal and reversible edges.