Pattern Reference
Bidirectional BFS
"Meet-in-the-middle on graphs. Word ladder, 8-puzzle, shortest path in large state spaces."
Loading...
Deep Dive Tutorial
Standard BFS expands O(b^d) nodes. Bidirectional BFS expands 2×O(b^(d/2)) = O(b^(d/2)) nodes — exponentially fewer when b is large. Key challenge: detecting when the two frontiers meet. Strategy: always expand the smaller frontier first (balanced expansion). When a node appears in both visited sets, check if the total path length improves the best known answer.
Bidirectional BFS template
function bidirBFS(start, end, getNeighbors) {
if (start === end) return 0;
let frontA = new Set([start]), frontB = new Set([end]);
let visitedA = new Map([[start, 0]]), visitedB = new Map([[end, 0]]);
let dist = 1;
while (frontA.size && frontB.size) {
// Always expand the smaller frontier
if (frontA.size > frontB.size) {
[frontA, frontB] = [frontB, frontA];
[visitedA, visitedB] = [visitedB, visitedA];
}
const nextA = new Set();
for (const node of frontA) {
for (const nei of getNeighbors(node)) {
if (visitedA.has(nei)) continue;
if (visitedB.has(nei)) return dist + visitedB.get(nei); // found!
visitedA.set(nei, dist);
nextA.add(nei);
}
}
frontA = nextA;
dist++;
}
return -1; // no path
}Worked Problems
↔
Bidirectional BFS vs standard BFS:
- Standard: O(b^d) nodes explored
- Bidirectional: O(b^(d/2)) nodes — exponentially better
- Best when: both start and end are known, branching factor b is large
Implementation tips:
- Always expand the smaller frontier (balances the two BFS trees)
- When a node appears in the opposite visited set: current_dist + opposite_dist = total path
- For unweighted graphs: can just check if next node is in the other frontier
Caution: Bidirectional Dijkstra (weighted) is more complex — simply finding a node in both sets isn't enough; must also check that all paths through that node are explored.
- Standard: O(b^d) nodes explored
- Bidirectional: O(b^(d/2)) nodes — exponentially better
- Best when: both start and end are known, branching factor b is large
Implementation tips:
- Always expand the smaller frontier (balances the two BFS trees)
- When a node appears in the opposite visited set: current_dist + opposite_dist = total path
- For unweighted graphs: can just check if next node is in the other frontier
Caution: Bidirectional Dijkstra (weighted) is more complex — simply finding a node in both sets isn't enough; must also check that all paths through that node are explored.