Bidirectional Search
Bidirectional Search is a graph traversal technique that simultaneously searches forward from the start node and backward from the goal node, meeting in the middle. This approach dramatically reduces the search space compared to standard BFS.
For unweighted graphs, bidirectional BFS finds the shortest path in roughly half the time of standard BFS.
Key Feature
Bidirectional search works by running two simultaneous breadth-first searches -- one from the start vertex and one from the goal vertex -- and stopping when they meet. This reduces the effective branching factor from b to b^(b/2).
How It Worksâ
Bidirectional search maintains two frontiers (queues) and two visited sets: one for the forward search and one for the backward search.
Stepsâ
- Initialize two queues: one for the forward search (starting from start node) and one for the backward search (starting from goal node).
- Initialize two visited sets to track visited nodes in each direction.
- While both queues are non-empty:
- Expand the smaller queue (alternating expansion to balance the search).
- For each node dequeued, check if it has been visited in the opposite direction.
- If an intersection is found, reconstruct the path by combining the forward and backward paths.
- If both queues are exhausted without meeting, no path exists.
Dry Run Exampleâ
Graph: A -- B -- C -- D -- E (a simple chain)
Start: A, Goal: E
Forward frontier: {A} Backward frontier: {E}
Visited FWD: {A} Visited BWD: {E}
Step 1 (expand smaller -- both equal, pick forward):
Dequeue A: neighbors = {B}
Forward frontier: {B}
Visited FWD: {A, B}
Step 2 (expand smaller -- backward):
Dequeue E: neighbors = {D}
Backward frontier: {D}
Visited BWD: {E, D}
Step 3 (expand forward):
Dequeue B: neighbors = {C}
Forward frontier: {C}
Visited FWD: {A, B, C}
Step 4 (expand backward):
Dequeue D: neighbors = {C}
C found in forward visited!
Intersection at C.
Path: A -> B -> C <- D <- E
Full path: A -> B -> C -> D -> E (length 4)
Complexity Analysisâ
| Metric | Standard BFS | Bidirectional BFS |
|---|---|---|
| Time Complexity | O(b^d) | O(b^(d/2)) |
| Space Complexity | O(b^d) | O(b^(d/2)) |
| Nodes explored | b^d | ~2 * b^(d/2) |
Where b = branching factor, d = distance from start to goal.
For a graph where b=2 and d=10:
- Standard BFS: ~2048 nodes
- Bidirectional BFS: ~2 * 2^5 = 64 nodes (32x fewer!)
Implementationâ
Pythonâ
from collections import deque
def bidirectional_bfs(graph, start, goal):
if start == goal:
return [start]
# frontiers
forward_q = deque([start])
backward_q = deque([goal])
# visited with parent tracking
forward_visited = {start: None}
backward_visited = {goal: None}
while forward_q and backward_q:
# Expand the smaller frontier
if len(forward_q) <= len(backward_q):
# Expand forward
current = forward_q.popleft()
for neighbor in graph.get(current, []):
if neighbor not in forward_visited:
forward_visited[neighbor] = current
if neighbor in backward_visited:
# Intersection found!
return reconstruct_path(
forward_visited, backward_visited, neighbor
)
forward_q.append(neighbor)
else:
# Expand backward
current = backward_q.popleft()
for neighbor in graph.get(current, []):
if neighbor not in backward_visited:
backward_visited[neighbor] = current
if neighbor in forward_visited:
# Intersection found!
return reconstruct_path(
forward_visited, backward_visited, neighbor
)
backward_q.append(neighbor)
return None # No path exists
def reconstruct_path(forward_visited, backward_visited, intersection):
# Reconstruct forward part: start -> intersection
path_forward = []
node = intersection
while node is not None:
path_forward.append(node)
node = forward_visited[node]
path_forward.reverse()
# Reconstruct backward part: intersection -> goal
path_backward = []
node = backward_visited[intersection]
while node is not None:
path_backward.append(node)
node = backward_visited[node]
return path_forward + path_backward
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['D']
}
path = bidirectional_bfs(graph, 'A', 'E')
print("Shortest path:", path) # ['A', 'D', 'E']
Javaâ
import java.util.*;
public class BidirectionalBFS {
public static List<String> bfs(Map<String, List<String>> graph,
String start, String goal) {
if (start.equals(goal)) return List.of(start);
Map<String, String> forwardParent = new HashMap<>();
Map<String, String> backwardParent = new HashMap<>();
Queue<String> forwardQ = new LinkedList<>();
Queue<String> backwardQ = new LinkedList<>();
forwardQ.offer(start);
backwardQ.offer(goal);
forwardParent.put(start, null);
backwardParent.put(goal, null);
while (!forwardQ.isEmpty() && !backwardQ.isEmpty()) {
// Expand forward
if (forwardQ.size() <= backwardQ.size()) {
String curr = forwardQ.poll();
for (String neighbor : graph.getOrDefault(curr, List.of())) {
if (!forwardParent.containsKey(neighbor)) {
forwardParent.put(neighbor, curr);
if (backwardParent.containsKey(neighbor))
return reconstruct(forwardParent, backwardParent, neighbor);
forwardQ.offer(neighbor);
}
}
} else {
// Expand backward
String curr = backwardQ.poll();
for (String neighbor : graph.getOrDefault(curr, List.of())) {
if (!backwardParent.containsKey(neighbor)) {
backwardParent.put(neighbor, curr);
if (forwardParent.containsKey(neighbor))
return reconstruct(forwardParent, backwardParent, neighbor);
backwardQ.offer(neighbor);
}
}
}
}
return null;
}
private static List<String> reconstruct(Map<String, String> fwd,
Map<String, String> bwd,
String meet) {
List<String> path = new ArrayList<>();
// Forward part
for (String at = meet; at != null; at = fwd.get(at))
path.add(0, at);
// Backward part (excluding meet)
String at = bwd.get(meet);
while (at != null) {
path.add(at);
at = bwd.get(at);
}
return path;
}
}
C++â
#include <bits/stdc++.h>
using namespace std;
vector<string> bidirectionalBFS(
const unordered_map<string, vector<string>>& graph,
const string& start, const string& goal
) {
if (start == goal) return {start};
queue<string> fwdQ, bwdQ;
unordered_map<string, string> fwdParent, bwdParent;
fwdQ.push(start);
bwdQ.push(goal);
fwdParent[start] = "";
bwdParent[goal] = "";
auto reconstruct = [&](const string& meet) {
vector<string> path;
for (string cur = meet; !cur.empty(); cur = fwdParent[cur])
path.push_back(cur);
reverse(path.begin(), path.end());
string back = bwdParent[meet];
while (!back.empty()) {
path.push_back(back);
back = bwdParent[back];
}
return path;
};
while (!fwdQ.empty() && !bwdQ.empty()) {
if (fwdQ.size() <= bwdQ.size()) {
string curr = fwdQ.front(); fwdQ.pop();
for (const string& nb : graph.at(curr)) {
if (!fwdParent.count(nb)) {
fwdParent[nb] = curr;
if (bwdParent.count(nb))
return reconstruct(nb);
fwdQ.push(nb);
}
}
} else {
string curr = bwdQ.front(); bwdQ.pop();
for (const string& nb : graph.at(curr)) {
if (!bwdParent.count(nb)) {
bwdParent[nb] = curr;
if (fwdParent.count(nb))
return reconstruct(nb);
bwdQ.push(nb);
}
}
}
}
return {};
}
JavaScriptâ
function bidirectionalBFS(graph, start, goal) {
if (start === goal) return [start];
const fwdVisited = new Map([[start, null]]);
const bwdVisited = new Map([[goal, null]]);
let fwdQueue = [start];
let bwdQueue = [goal];
const expand = (queue, visited, otherVisited, isForward) => {
const current = queue.shift();
for (const neighbor of (graph[current] || [])) {
if (!visited.has(neighbor)) {
visited.set(neighbor, current);
if (otherVisited.has(neighbor)) {
return reconstruct(visited, otherVisited, neighbor);
}
queue.push(neighbor);
}
}
return null;
};
const reconstruct = (fwd, bwd, meet) => {
const path = [];
for (let n = meet; n !== undefined; n = fwd.get(n))
path.unshift(n);
let n = bwd.get(meet);
while (n !== undefined) {
path.push(n);
n = bwd.get(n);
}
return path;
};
while (fwdQueue.length > 0 && bwdQueue.length > 0) {
if (fwdQueue.length <= bwdQueue.length) {
const result = expand(fwdQueue, fwdVisited, bwdVisited, true);
if (result) return result;
} else {
const result = expand(bwdQueue, bwdVisited, fwdVisited, false);
if (result) return result;
}
}
return null;
}
Limitationsâ
- Bidirectional BFS requires knowing the goal node, making it suitable for point-to-point shortest path.
- Graph must be reversible: Works only if every edge can be traversed in both directions.
- Overhead: Two search frontiers and parent tracking add implementation complexity.
- Sparse graphs near goal: The speedup may be less significant in graphs where the goal is near the start.
Applicationsâ
- GPS Navigation: Finding the shortest route between two locations.
- Network Routing: Shortest path in network topology.
- Puzzle Solving: 8-puzzle, 15-puzzle, Rubik's cube (already using bidirectional search in IDA*).
- Web Crawlers: Bidirectional crawling from both seed URLs and target domain.
- AI Game Playing: Real-time strategy games where two opposing sides are searching for a meeting point.
Key Takeawaysâ
- Bidirectional search reduces exponential search to approximately square-root of the original cost.
- It requires simultaneous searches from both the start and goal nodes.
- The algorithm guarantees the shortest path in unweighted graphs.
- Expanding the smaller frontier at each step balances the two searches for maximum efficiency.
- It is particularly powerful when the goal is far from the start node.
Track Your Progress
Done with this topic? Mark it as complete to track your progress.