Pattern Guide
Bidirectional BFS
"BFS from both source and target. Meet in the middle. Reduces O(b^d) to O(b^(d/2))."
Bidirectional BFS runs two simultaneous BFS expansions: one from the source, one from the target. When the two frontiers overlap, the shortest path is found. Reduces the search space from O(b^d) to O(b^(d/2)) where b is the branching factor and d is the distance. Essential for word ladder problems, maze shortest paths, and any unweighted graph where both endpoints are known.
Problems you can solve with this pattern
3 problems · click any to start solving
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
}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.
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
}- 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.