Bidirectional breadth-first search: the idea
Prerequisites: Breadth-first search and reconstructing a predecessor chain.
Two breadth-first searches run on the same graph, one from the start and one from the destination. Each has its own queue, distances, and predecessor links. This implementation alternates complete layers. When newly discovered nodes appear in both searches, it keeps the meeting with the smallest sum of the two edge distances and finishes the current layer before returning. It then joins the start-to-meeting chain to the meeting-to-destination chain. Completing layers preserves the fewest-edge guarantee.
Try it on the same input
Start at A and aim for I. Cyan begins at A and amber begins at I. Watch B and C enter the start queue while G and H enter the goal queue. Inspect both distance tables and follow their arrows. The searches meet after expanding toward the center; the result joins two partial routes. Add an A–I connection with weight 99 to see that this algorithm, like BFS, prefers a single expensive edge over a cheaper route with more edges.
When to use it—and what to watch
Weights are ignored. The destination must be known and reverse exploration must be possible. Undirected connections here make reverse exploration straightforward; a directed graph would require incoming edges on the goal side. Two-way search can reduce exploration, but is not faster on every graph.
Time and memory
V means the number of nodes; E means the number of edges. O(V + E) with adjacency lists; two searches still require O(V) memory. These finite graph searches store visited-node information, predecessors, and a stack or frontier, requiring O(V) search memory.
The executable teaching version deliberately uses arrays: it scans the edge list to find neighbors and, for priority-based searches, sorts the frontier to select a minimum. It therefore does not achieve the adjacency-list or heap bounds quoted above. Recorded playback also stores a snapshot at each operation, using more memory than the search itself. The fixed nine-node graph keeps this small and makes the state easy to inspect.
Reading the display
Cyan tracks the start-side queue and predecessor links; amber tracks the goal-side search. Each distance table measures edges from its own endpoint. A node can appear in both searches. “Toward goal” points to the next node on the goal-side predecessor chain. The final green route joins both chains. A fewest-edge route need not have the lowest total weight.
For frontier-based searches, the frontier contains discovered nodes waiting to be explored. “Previous” records the predecessor used to reach a node. Dashed cyan arrows point back to those predecessors. ∞ means no route to that node has been discovered yet. Pink marks the current node or inspected connection; green marks the completed path. All connections are undirected: you can travel either way.
The Code panel shows explanatory pseudocode. The linked JavaScript is the executable implementation that produces every playback frame. A step can check a condition without changing the table; watch the highlighted line and explanation together.
Continue exploring
- Breadth-first search — Explore one layer at a time. Find a path with the fewest edges.
- Dijkstra’s algorithm — Explore the cheapest known route first. Minimize total weight.
- A* search — Combine cost so far with an estimate of the journey remaining.
- Depth-first search — Follow one branch deeply, then backtrack when it runs out.
- Greedy best-first search — Head toward the most promising-looking node, ignoring cost already paid.