CoreSource checked

Bidirectional Search

Searches from both the start and goal until the frontiers meet.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Meet-in-the-Middle Search
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

Bidirectional Search can reduce explored nodes by growing two smaller search frontiers instead of one large one.

Core Concepts

graph representationcandidate searchtwo-ended frontiertraversal ordermeet-in-the-middle searchvisited setfrontier expansion

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(b^(d/2))

Average

O(b^(d/2))

Worst

O(b^d)

Space

O(b^(d/2))

When to Use

Use Bidirectional Search when you need to expand from the start and goal.
Use it for shortest paths in unweighted graphs with inputs like graph.
Use it when relationships are naturally modeled as nodes connected by edges.
Use it when the Meet-in-the-Middle Search tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the graph is so large that storing every visited node is not practical.
Avoid it when O(b^d) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not path between start and goal.

What It Does

Expands from the start and goal
Stops when the frontiers intersect

Use Cases

Shortest paths in unweighted graphs
Word ladders
State-space search with known goal

Inputs

Graph
Start node
Goal node

Outputs

Path between start and goal
No-path result

Pseudocode

1.Create a frontier from the start
2.Create a frontier from the goal
3.Expand the smaller frontier
4.Check for overlap between visited sets
5.Reconstruct the path when the frontiers meet

Canonical Example

Input: graph = {A: [B, C], B: [D], C: [], D: []}, start = A
Output: visited = [A, B, C, D]
Explanation: Bidirectional Search: The traversal starts at A and visits reachable nodes by following edges.

Implementation Notes

Keep the input contract explicit: Graph; Start node; Goal node.
Use this step as the implementation spine: Create a frontier from the start.
Then preserve the next state change: Create a frontier from the goal.
Keep node ids, edge direction, and visited state explicit in the implementation.
Represent neighbors consistently and keep traversal state separate from the graph data.

Common Pitfalls

It works best when predecessors can be generated as easily as successors.
Not defining directed versus undirected edges clearly can change the result.
Forgetting to mark visited nodes before revisiting cycles or shared neighbors.
Returning path between start and goal without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show two expanding frontiers meeting in the middle.

Step 1 of 5: Create a frontier from the start

meeting-frontiers

Notes

Bidirectional Search operates in O(b^(d/2)) time and O(b^(d/2)) space within the Meet-in-the-Middle Search family. Often compared with Breadth-First Search and A* Search.