Course contentsShow
← Computer Science
Lesson 707 of 2,87217. Graph Traversal AlgorithmsFree lesson

Bidirectional BFS

Searching from both ends simultaneously: meeting in the middle, significant speedup for shortest path queries.

Bidirectional BFS

What You'll Learn

You'll learn how to dramatically speed up shortest-path searches by running BFS from both the start and goal simultaneously until they meet in the middle.

The Core Idea

Traditional BFS explores outward from a single source like ripples in a pond. Bidirectional BFS launches two simultaneous searches—one from the start vertex and one from the goal vertex—expanding both frontiers until they collide.

Think of it like two people searching for each other in a maze: instead of one person walking the entire path, both start from opposite ends and meet halfway. This cuts the search space dramatically.

Why It's Faster

If the shortest path has length d, regular BFS explores roughly b^d nodes (where b is the branching factor). Bidirectional BFS explores b^(d/2) nodes from each end, totaling approximately 2 × b^(d/2) nodes.

For example, with branching factor 10 and path length 6:

  • Regular BFS: ~1,000,000 nodes
  • Bidirectional BFS: ~2,000 nodes (500× faster!)

How It Works

  1. Initialize two queues: one from the start, one from the goal
  2. Alternate expanding one level from each frontier
  3. Track visited nodes separately for each direction
  4. Stop when the frontiers intersect—you've found the shortest path
  5. Reconstruct the path by joining the two halves

When to Use It

Bidirectional BFS shines when:

  • You know both start and end vertices
  • The graph is unweighted (or use 0-1 BFS for edge weights 0/1)
  • You need shortest paths in large graphs

Key Takeaway: Bidirectional BFS meets in the middle, reducing exponential search space from b^d to roughly 2 × b^(d/2), offering dramatic speedups for shortest-path queries when both endpoints are known.