Uninformed search

Bidirectional Search (BDS)

Dig from both ends of the tunnel and meet in the middle.

On the Sydney → London problem, Bidirectional Search finds: Sydney → Singapore → Doha → London — total 23.0h.

The idea

Bidirectional Search runs two searches at the same time: one going forward from the start, and one going backward from the goal. Each search grows its own frontier, and the moment the two frontiers touch, you stitch their paths together into one full route. Because each side only has to travel half the distance, you explore far fewer options than searching all the way from one end.

How it works

Put the START node in the forward OPEN list, and the GOAL node in the backward OPEN list. Both CLOSED lists start empty.
Expand one node from the forward side: take it off forward OPEN, add it to forward CLOSED, and put its neighbors on forward OPEN.
Expand one node from the backward side the same way, but follow moves in reverse (which is why moves must be reversible).
After each expansion, check whether the node you just reached already appears in the other side's CLOSED (or OPEN). If it does, the two searches have met.
When they meet at a shared node, stop: build the answer by joining the forward path (start to meeting node) with the backward path (meeting node to goal).
If they haven't met, alternate sides — keep expanding forward, then backward, one layer at a time using BFS on each side.
Keep going until the frontiers meet (success) or both OPEN lists empty out (no path exists).

See it step by step

Watch Bidirectional Search search a real problem — flying from Sydney (SYD) to London (LHR). Click Next to advance one expansion and watch OPEN, the traversal, the path and the cost update live.

Start at Sydney. OPEN (the frontier) holds just Sydney.

Expanding

OPEN — frontier

CLOSED — traversal

Path so far

Cost so far

Step 1 / 4

OPEN, CLOSED & the data structures

Each direction has its own OPEN (the frontier of nodes waiting to be expanded) and its own CLOSED (nodes already expanded). Since we use BFS on both sides, each OPEN is a FIFO queue, so nodes come out in the order they were discovered — nearest first. The two CLOSED lists do double duty: they record where each search has been, and they are what you check against to detect the moment the searches overlap.

Pseudocode

function BidirectionalSearch(start, goal):
    OPEN_f = queue([start]);   CLOSED_f = {}      # forward, from start
    OPEN_b = queue([goal]);    CLOSED_b = {}      # backward, from goal

    while OPEN_f not empty and OPEN_b not empty:
        # --- expand one node from the forward side ---
        n = OPEN_f.dequeue();   CLOSED_f.add(n)
        if n in CLOSED_b: return join(n)           # frontiers met
        for m in neighbors(n):
            if m not in CLOSED_f: OPEN_f.enqueue(m)

        # --- expand one node from the backward side ---
        n = OPEN_b.dequeue();   CLOSED_b.add(n)
        if n in CLOSED_f: return join(n)           # frontiers met
        for m in reverse_neighbors(n):
            if m not in CLOSED_b: OPEN_b.enqueue(m)

    return failure                                 # no path exists

At a glance

Complete?Yes — with BFS on both sides it always finds a path if one exists, because both frontiers explore every layer without missing nodes.

Optimal?Yes, optimal in number of steps — BFS on each half guarantees the shortest path when every move costs the same (with care taken at the meeting point).

TimeO(b^(d/2)) — each side only searches to half the depth, so instead of b^d you get roughly two searches of b^(d/2); a huge saving.

SpaceO(b^(d/2)) — you must keep both frontiers (OPEN) and both visited sets (CLOSED) in memory, but each only reaches half the depth, so far less than one-directional BFS.

👍 When to use it

You know exactly what the goal is (not just a test for it), so you can start searching backward from it
Moves are reversible — you can work backward from the goal the same way you work forward
The graph is deep and branchy, where one-directional BFS would blow up as b^d
You want BFS's shortest-path guarantee but can't afford its memory or time cost

⚠️ Watch out for

You must have an explicit goal state to start the backward search — if the goal is only described by a test ("any winning board"), you can't search backward from it.
Moves must be reversible; if you can't undo a move, the backward search has nothing to follow.
Detecting the meeting point is the tricky part — check each newly expanded node against the other side's CLOSED, and don't stop at the very first touch without confirming it gives the shortest combined path.
Keeping two OPEN and two CLOSED lists in sync is more bookkeeping than a plain one-directional search — it's easy to check the wrong side's list.

Now see it for yourself

Open Bidirectional Search in the visualizer — step through it, pause, and watch OPEN & CLOSED change.

▶ Watch it run