Uninformed search

Breadth-First Search (BFS)

Explore a maze one ripple at a time, nearest first.

On the Sydney → London problem, Breadth-First Search finds: Sydney → Singapore → Dubai → London — total 22.5h.

The idea

Breadth-First Search (BFS) is an uninformed search: it knows nothing about which direction the goal lies, so it fairly explores outward from the start. It looks at everything one step away, then everything two steps away, and so on, level by level. Because it never skips a closer node to try a farther one, the first time it reaches the goal it has used the fewest possible steps (edges).

How it works

Put the start node in OPEN (the frontier of nodes waiting to be expanded) and mark it seen.
Take the node from the FRONT of OPEN (the oldest one waiting). Call it 'current'.
If current is the goal, stop and rebuild the path by following each node back to its parent.
Otherwise 'expand' current: look at all its neighbours.
For each neighbour not already seen, record current as its parent and add it to the BACK of OPEN.
Move current into CLOSED (already-expanded/visited nodes) so it is never processed again.
Repeat from step 2 until the goal is found or OPEN is empty (meaning no path exists).

See it step by step

Watch Breadth-First 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 / 8

OPEN, CLOSED & the data structures

OPEN is a FIFO queue (First In, First Out): new nodes join the back and we always take from the front, which is exactly what forces the level-by-level order. CLOSED is a set of already-expanded nodes; we check it (plus nodes already sitting in OPEN) before adding a neighbour so we never enqueue the same node twice and never loop forever. Together, OPEN holds the growing ripple's edge and CLOSED holds everything the ripple has already passed through.

Pseudocode

BFS(start, goal):
    OPEN  <- empty FIFO queue
    CLOSED <- empty set
    enqueue start into OPEN
    mark start as seen; parent[start] <- none
    while OPEN is not empty:
        current <- dequeue front of OPEN
        if current == goal:
            return reconstruct_path(parent, goal)
        add current to CLOSED
        for each neighbour n of current:
            if n not seen:            # not in OPEN and not in CLOSED
                mark n as seen
                parent[n] <- current
                enqueue n into OPEN
    return failure                    # OPEN emptied, goal unreachable

At a glance

Complete?Yes, complete: if a path exists it is guaranteed to find it, because the ripple eventually reaches every node.

Optimal?Partly: optimal in number of edges (fewest steps), but NOT optimal in path cost when edges have different weights.

TimeO(b^d) — with branching factor b and goal depth d, the number of nodes explored grows exponentially with depth.

SpaceO(b^d) — the whole frontier of a level must sit in OPEN at once, so memory is the real bottleneck, not time.

👍 When to use it

You want the shortest path counted in steps and every step costs the same.
The graph isn't too deep, so the memory blow-up stays manageable.
You have no clue where the goal is (no heuristic), so exploring fairly is fine.
You need a guaranteed answer: it will find a path if one exists.

⚠️ Watch out for

Memory, not speed, is what usually kills BFS: OPEN can hold a whole exponential level at once.
It is NOT cost-optimal on weighted edges. Fewest steps is not always cheapest, use Uniform-Cost Search / Dijkstra for weights.
Mark a node as seen the moment you enqueue it, not when you dequeue it, or the same node gets added many times.
Always take from the FRONT and add to the BACK. Mixing this up turns BFS into a different algorithm entirely.

Now see it for yourself

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

▶ Watch it run