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
- Initialize two queues: one from the start, one from the goal
- Alternate expanding one level from each frontier
- Track visited nodes separately for each direction
- Stop when the frontiers intersect—you've found the shortest path
- 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.