vault

Bidirectional BFS

16 min read

Bidirectional BFS

Bidirectional Breadth-First Search (Bidirectional BFS, often abbreviated BiBFS) is a shortest-path search that runs two simultaneous breadth-first searches — one expanding outward from the source s, the other expanding outward from the target t — and terminates as soon as the two search frontiers touch. For a graph with branching factor b (average number of neighbors per node) and shortest-path length d (number of edges in the optimal path), bidirectional BFS visits roughly O(b^(d/2)) nodes instead of plain BFS’s O(b^d). Because b^(d/2) + b^(d/2) ≪ b^d for any non-trivial d, the speedup is enormous on the large implicit state-space graphs that appear in word-ladder problems, social-network distance queries, and game-state search. The algorithmic trick is conceptually simple, but the termination condition and the frontier-swap heuristic are easy to get wrong; this note dwells on both.

1. Intuition — Two People Digging a Tunnel from Both Ends

Imagine you’re digging a tunnel between two mountain villages, s and t. The straightforward approach is to start at s and dig toward t. If the villages are 1000 metres apart and you can clear 10 m³ of rock per metre of tunnel (the “branching factor” — how much rock fans out around each step), you’ll move roughly 10^1000 cubic metres of rock. Awful.

Now imagine you put one crew at s and another at t, and they dig toward each other. Each crew only has to cover 500 metres before they meet in the middle, so each crew moves 10^500 cubic metres — and although you have two crews, 2 × 10^500 ≪ 10^1000. The total work is square-rooted.

That’s bidirectional BFS exactly. The “tunnel” is the shortest path, the “rock” is the BFS frontier (set of nodes at the current expansion depth), and “meeting in the middle” is the moment the two frontiers share a node — at which point the shortest path through that meeting node is the answer.

The only subtlety is that real shortest paths don’t always split evenly: sometimes the source side has a much higher branching factor than the target side (or vice versa). The algorithm fixes this by always expanding the smaller frontier next — a greedy heuristic that keeps the two halves balanced in frontier size, which is what actually drives the time cost.

2. Tiny Worked Example

Consider this unweighted graph and find the shortest path from A to H:

A — B — C — D — E — F — G — H
        |               |
        J ————————————— K

Adjacency (undirected):

A: [B]              B: [A, C]              C: [B, D, J]
D: [C, E]           E: [D, F]              F: [E, G]
G: [F, H, K]        H: [G]                 J: [C, K]
K: [J, G]

The optimal path A → B → C → J → K → G → H has length 6.

Plain BFS from A

StepFrontierVisited size
0{A}1
1{B}2
2{C}3
3{D, J}5
4{E, K}7
5{F, G}9
6{H} — target found10

Plain BFS examined 10 nodes.

Bidirectional BFS from A and H

StepForward frontier (from A)Backward frontier (from H)Visited
0{A}{H}{A, H}
1 (forward){B}{H}{A, B, H}
1 (backward){B}{G}{A, B, G, H}
2 (forward){C}{G}{A, B, C, G, H}
2 (backward){C}{F, K}{A, B, C, F, G, H, K}
3 (forward){D, J}{F, K}—

At step 3, when we expand the forward frontier {C} and add neighbours {D, J}, we check whether either is in the backward visited set. J is not (yet), but on the next expansion of the backward frontier {F, K}, the neighbours of K include J. So we’d find J from both sides.

Alternative: at step 2 backward, neighbours of G were {F, H, K}; we added F and K to the backward visited set. Now when we expand the forward frontier {D, J}, neighbour K of J is already in the backward visited set — frontiers meet at K. Total path length = dist_forward[J] + 1 + dist_backward[K] = 3 + 1 + 2 = 6. ✓

Bidirectional BFS visited around 7 nodes versus plain BFS’s 10. On this trivially small graph the savings look modest, but on a graph where each node has 10 neighbours and the path length is 12, plain BFS visits ≈ 10^12 nodes whereas BiBFS visits ≈ 2 × 10^6 — a million-fold reduction.

3. Pseudocode

bidirectional_bfs(graph, source, target):
    if source == target:
        return 0
    visited_s := {source}        # nodes reached from source
    visited_t := {target}        # nodes reached from target
    frontier_s := {source}
    frontier_t := {target}
    distance := 0
    while frontier_s is not empty AND frontier_t is not empty:
        # always expand the smaller frontier next (load balancing)
        if |frontier_s| > |frontier_t|:
            swap(frontier_s, frontier_t)
            swap(visited_s, visited_t)
        distance := distance + 1
        next_frontier := empty set
        for each u in frontier_s:
            for each neighbour v of u:
                if v in visited_t:
                    return distance              # frontiers meet
                if v not in visited_s:
                    visited_s.add(v)
                    next_frontier.add(v)
        frontier_s := next_frontier
    return -1                                    # unreachable

The if v in visited_t: return distance line is the meet check. The early-return correctness depends critically on expanding one full layer at a time on each side, then checking. Mixing layer-by-layer on one side with node-by-node on the other side breaks the optimality guarantee.

4. Python Implementation

from collections import deque
 
def bidirectional_bfs(graph, source, target):
    """
    graph: dict mapping node -> iterable of neighbours
    source, target: hashable nodes
    Returns: length of shortest path (number of edges), or -1 if unreachable
    """
    if source == target:
        return 0
    visited_s = {source}
    visited_t = {target}
    frontier_s = {source}
    frontier_t = {target}
    dist = 0
    while frontier_s and frontier_t:
        # always expand the smaller frontier (heuristic — keeps the two
        # exponential trees balanced; minimises total nodes visited)
        if len(frontier_s) > len(frontier_t):
            frontier_s, frontier_t = frontier_t, frontier_s
            visited_s, visited_t = visited_t, visited_s
        dist += 1
        next_frontier = set()
        for u in frontier_s:
            for v in graph[u]:
                if v in visited_t:
                    return dist                  # frontiers meet -> done
                if v not in visited_s:
                    visited_s.add(v)
                    next_frontier.add(v)
        frontier_s = next_frontier
    return -1

Reconstructing the actual path (not just the length)

Path reconstruction is messier than for plain BFS because you need a parent map on both sides plus knowledge of which node was the meeting point:

def bidirectional_bfs_path(graph, source, target):
    if source == target:
        return [source]
    parent_s = {source: None}
    parent_t = {target: None}
    frontier_s = {source}
    frontier_t = {target}
 
    def step(frontier, parent, other_parent):
        next_frontier = set()
        for u in frontier:
            for v in graph[u]:
                if v in other_parent:
                    return v, next_frontier      # meeting node found
                if v not in parent:
                    parent[v] = u
                    next_frontier.add(v)
        return None, next_frontier
 
    while frontier_s and frontier_t:
        if len(frontier_s) <= len(frontier_t):
            meet, frontier_s = step(frontier_s, parent_s, parent_t)
            if meet:
                return _stitch(meet, parent_s, parent_t)
        else:
            meet, frontier_t = step(frontier_t, parent_t, parent_s)
            if meet:
                return _stitch(meet, parent_s, parent_t, reverse=True)
    return None
 
def _stitch(meet, parent_s, parent_t, reverse=False):
    # walk back from meet to source via parent_s
    left = []
    n = meet if meet in parent_s else parent_s[meet]
    # ...this is fiddly; see Pitfalls §9.4 for why
    raise NotImplementedError("see pitfalls")

The reconstruction code is the part that catches people in interviews. The cleanest pattern is to maintain parent_s[v] = u such that (u, v) is the forward edge that discovered v, and the symmetric thing on the backward side. The meeting node m then has a forward chain m → parent_s[m] → ... → source and a backward chain m → parent_t[m] → ... → target; concatenate them with care about which side discovered m.

5. Complexity

Let b be the branching factor — the average number of neighbours per node — and d be the shortest-path distance in number of edges from source to target. Plain BFS, in the worst case, explores essentially every node within distance d of the source. The number of nodes within distance d in a tree of branching factor b is 1 + b + b² + ... + b^d ≈ b^d. So plain BFS time is O(b^d) (and similarly O(b^d) space for the visited set in the worst case).

Bidirectional BFS runs two simultaneous searches, each only needing to reach the midpoint. Each search reaches depth d/2, exploring O(b^(d/2)) nodes. Total:

T_BiBFS = O(b^(d/2)) + O(b^(d/2)) = O(b^(d/2))

The space cost is also O(b^(d/2)) because both frontiers and visited sets must fit in memory at once.

Why this is dramatic

  • b = 10, d = 6: plain BFS visits 10^6 = 1,000,000 nodes; BiBFS visits 2 × 10^3 = 2,000. 500× speedup.
  • b = 26, d = 10 (e.g. word-ladder over 5-letter words): plain BFS visits ≈ 1.4 × 10^14; BiBFS visits ≈ 2 × 10^7. 7-million-fold speedup.

Caveats — when BiBFS does not help

  1. d is small (say, ≤ 3). Constants and bookkeeping overhead can outweigh b^(d/2) → b^d savings.
  2. b_forward ≠ b_backward — if the predecessor function (neighbours-pointing-toward-v) is hard to compute, the backward search might be impossibly slow. For unweighted, undirected graphs the predecessors equal the successors, so this is not an issue. For directed graphs you need both the forward adjacency and the reverse adjacency — extra storage.
  3. The graph is highly asymmetric (e.g. backward search from t immediately hits a high-branching region while forward search from s is in a narrow region). The frontier-swap heuristic mitigates but doesn’t fully fix this.
  4. The state representation is so large that doubling the visited-set memory is prohibitive. Then plain BFS or Iterative Deepening DFS (which uses O(d) memory) may be necessary.

Where the O(b^(d/2)) bound actually holds. This bound is derived under the simplified tree-shaped state-space model — explicitly noted in the Wikipedia article on bidirectional search, which frames the analysis as “a simplified model of search problem complexity in which both searches expand a tree with branching factor b.” On a real graph with cycles, the visited set deduplicates revisits, so the actual cost is O(min(b^(d/2), V)) — i.e., the bound is tight only while the expanding frontier hasn’t yet saturated the reachable subgraph. For bounded-diameter highly connected graphs (small-world graphs, complete-ish graphs), both BFS and BiBFS approach O(V + E) and the asymptotic speedup vanishes; the constant-factor improvement (touching roughly half as many nodes) can still be meaningful in practice.

6. Termination — The Subtle Part

A naive implementation that returns the moment a node v appears in both visited sets has a bug: it might not return the shortest path. The correct termination protocol:

  1. Expand one full layer on the chosen side (forward or backward) before checking for intersection.
  2. If during the layer’s expansion a neighbour v is seen on the other side’s visited set, return dist_forward + 1 + dist_backward[v]. The +1 accounts for the edge (u, v) that crossed the boundary.
  3. If multiple meeting nodes are found in the same layer, take the one giving the smallest total distance. (For unweighted graphs all are tied; for weighted variants, this matters.)

A subtle gotcha: if you check intersection before expanding the layer (i.e., immediately on dequeue rather than on enqueue), you might return a path that’s one edge longer than necessary. The correct invariant is “the distance returned is forward_layer_count + 1 + backward_layer_count_when_v_was_added.”

For weighted graphs the termination condition is even harder — you cannot stop at the first frontier intersection; you must continue until the sum of the two minimum-frontier distances equals or exceeds the best path found so far. This generalisation is bidirectional Dijkstra, related to but distinct from BiBFS; see Dijkstra’s Algorithm §7.4.

7. Use Cases

7.1 Word Ladder (LeetCode 127)

Given two words beginWord and endWord and a dictionary, find the shortest transformation sequence where each step changes one letter and each intermediate word must be in the dictionary. The implicit graph has one node per dictionary word; two words are adjacent if they differ by exactly one letter. With a 5,000-word dictionary and a 5-letter word, plain BFS can hit ~25 neighbours per node and >10 layers deep — millions of states. Bidirectional BFS reduces this to thousands and is the standard accepted solution; the LeetCode editorial explicitly recommends it for performance.

7.2 Social Network Distance Queries

“What is the degree of separation between user A and user B?” On a network of millions of users with average friend count ~200, plain BFS to depth 6 (the famous “six degrees”) explores 200^6 = 6.4 × 10^13 candidates. BiBFS explores 2 × 200^3 = 1.6 × 10^7. Facebook’s friend-graph queries historically used variants of this approach.

7.3 Sliding-Puzzle Solving (8-puzzle, 15-puzzle)

Each board configuration is a node; adjacent configurations differ by one tile slide. The 15-puzzle has ~10^13 reachable states; plain BFS quickly exhausts memory. Bidirectional BFS plus heuristics (A-Star Search or IDA* — see Iterative Deepening DFS) is the standard approach.

7.4 Game-State Search (Rubik’s Cube, Theorem Proving)

Korf’s classic 1997 paper “Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases” used IDA* rather than BiBFS because the cube’s state space is 4.3 × 10^19 states — too large for BiBFS’s memory. But for smaller game-state problems (Sokoban with small boards, simple chess endgames, planning under STRIPS-like operators), BiBFS is competitive and simpler than IDA*.

7.5 Network Routing

Finding the shortest cable route between two endpoints in a network topology. Often combined with hierarchical pre-computation (contraction hierarchies) for road networks; pure BiBFS appears in simpler topologies.

8. Comparison to Other Shortest-Path Algorithms

AlgorithmEdge weightsBest forComplexity
Breadth-First Searchunweightedsmall to medium graphsO(V+E)
Bidirectional BFSunweightedvery large implicit graphs, single (s, t) queryO(b^(d/2))
Dijkstra’s Algorithmnon-negative weightsweighted single-sourceO((V+E) log V)
Bidirectional Dijkstranon-negative weightsvery large weighted graphs, single (s, t)typically halves work
A-Star Searchnon-negative + heuristicguided search, e.g. pathfindingO(b^d) but with much smaller constant
Iterative Deepening DFSunweightedhuge state spaces, memory-boundO(b^d) time, O(d) space

When you have a single source-target query on an unweighted graph and the path length might be 5+, BiBFS is almost always the right call. For all-pairs or single-source-many-targets queries, plain BFS wins because BiBFS would have to be re-run for each pair.

9. Pitfalls

9.1 Returning at first frontier-set intersection without layer discipline

Checking if visited_s ∩ visited_t: return between expansion steps can return non-shortest paths because you might miss a shorter route that would appear in the next half-step. Always expand a full layer on one side, then check intersections.

9.2 Forgetting to handle source == target

Edge case: if source == target, return 0 immediately. Without this guard, the loop initializes both visited sets to {source} and the intersection check might never fire (the algorithm still terminates, but distance computation is wrong).

9.3 Directed graphs without reverse adjacency

The backward search needs predecessors, not successors. For a directed graph stored as forward adjacency graph[u] = [v1, v2, ...], the backward search from t needs predecessors[t] = [u1, u2, ...] — which means pre-computing the reverse graph. Many implementations silently do the wrong thing by reusing the forward adjacency in both directions; this works for undirected graphs but is wrong for directed.

9.4 Path reconstruction bugs

Stitching the two parent chains together is error-prone. Common bugs:

  • Off-by-one when counting the meeting edge.
  • Forgetting to reverse one of the two chains.
  • Including the meeting node twice (once from each chain).

The cleanest test: write a tiny graph by hand, run the algorithm, manually verify the returned path has exactly dist edges and starts at source, ends at target.

9.5 Frontier-swap heuristic mishandled when one side is empty

If frontier_s becomes empty (e.g., the source’s component has been fully explored without finding t), the algorithm should return -1 immediately rather than swapping to the other (still non-empty) side. The condition while frontier_s and frontier_t handles this correctly only because both must be non-empty to continue.

9.6 Visited set membership for hashable states

In game-state search, the “node” might be a board configuration represented as a tuple-of-tuples or a frozenset. These are slow to hash. For very large searches, serializing to a compact string or a single integer encoding can deliver a 10× speedup unrelated to the algorithm itself.

9.7 Memory blowup despite the speedup

BiBFS visits fewer nodes total than plain BFS, but it must hold both frontiers and both visited sets simultaneously. For pathological graphs where one side’s frontier is huge while the other side’s is tiny, you can OOM where plain BFS would have completed. The frontier-swap heuristic mitigates this, but watch memory.

10. Diagram — Two Frontiers Meeting

flowchart LR
  S((Source)) -->|layer 1| A1((A1))
  S -->|layer 1| A2((A2))
  A1 -->|layer 2| B1((B1))
  A1 -->|layer 2| B2((B2))
  A2 -->|layer 2| B3((B3))
  B1 -->|layer 3| M((MEET))
  B3 -->|layer 3| M
  T((Target)) -->|layer 1| C1((C1))
  T -->|layer 1| C2((C2))
  C1 -->|layer 2| D1((D1))
  C2 -->|layer 2| M

What this diagram shows. Two breadth-first searches grow simultaneously: the forward search expands outward from Source (left), reaching nodes labelled by increasing distance (A1, A2 at layer 1; B1, B2, B3 at layer 2; MEET at layer 3). The backward search expands outward from Target (right), reaching C1, C2 at layer 1; D1, MEET at layer 2. The node MEET is reachable from both — it’s the meeting point. The total shortest-path length from Source to Target through MEET is forward_distance(MEET) + backward_distance(MEET) = 3 + 2 = 5. The key insight: each search traverses only d/2 = 2.5 ≈ 3 layers on average, so each side visits a small fraction of what plain BFS from Source to Target (5 layers deep) would visit.

11. Common Interview Problems

LeetCode #ProblemWhy BiBFS helps
127Word LadderImplicit graph; large dictionary; ~10-letter ladders blow up plain BFS
126Word Ladder IIAll shortest transformations; BiBFS for length, then DFS to enumerate
752Open the Lock4-digit lock; 10,000 states; BiBFS halves work
433Minimum Genetic Mutation8-letter genes over 4 nucleotides; same shape as Word Ladder
1345Jump Game IVJumps to same-value indices; meet-in-the-middle when graph is big
815Bus RoutesImplicit graph of bus stops; routes form layers

The dead giveaway for BiBFS in interviews: the problem says “shortest path / fewest steps” and the state space is implicit and combinatorially large and both endpoints are known.

12. Open Questions

  • When does asymmetric branching (e.g., predecessors much sparser than successors) make BiBFS slower than plain BFS? Quantify the crossover point.
  • How does BiBFS interact with bloom-filter-based visited sets when memory is the binding constraint?
  • Is there a clean termination condition for BiBFS on graphs with negative-weight edges? (Probably not — that’s Bellman-Ford territory and bidirectional Bellman-Ford is rarely useful.)

13. See Also

Graph View

Backlinks