Breadth-first search

August 4, 2026

Breadth-first search has no idea where the goal is. It examines every cell one move from the start, then every cell two moves away, and continues until the goal turns up.

Click anywhere to move the goal.

The shaded region is a disc, because BFS grows outward at the same rate in every direction. That shape is the algorithm.

The rule

Keep a queue of discovered cells. Take from the front, add to the back.

That is the entire specification. Everything BFS guarantees follows from it, because a queue hands cells back in the order they were discovered, and cells are discovered in order of distance from the start.

Why the first route found is the shortest

Let $d(n)$ be the fewest moves from the start to cell $n$.

BFS expands cells in non-decreasing $d$. When it takes a cell off the queue, it has already taken every cell with a smaller $d$, and it discovers each cell’s neighbours at $d + 1$. So the queue holds cells of depth $d$ and $d + 1$ and never anything further, and the first time the goal is discovered, it is at its minimum depth.

Turn on step counts in the tool and watch the numbers come off in order. They never go down.

The marking matters. A cell is marked the moment it is discovered, not when it is expanded. Without that, the same cell enters the queue once per neighbour that sees it, and the queue grows with the number of edges rather than the number of cells.

Shortest in moves is not cheapest

BFS counts moves. It does not know that a diagonal step costs $\sqrt{2}$ while a straight one costs $1$.

Here that distinction is smaller than it sounds. The fewest-move route across open ground uses as many diagonals as it can, and so does the cheapest route, so the two objectives usually agree on this grid. They agree because $\sqrt{2} < 2$: one diagonal beats the two straight moves it replaces.

Change that pricing and they come apart immediately. If a diagonal cost $3$, the fewest-move route would still take it and would no longer be the cheapest. This is the real limitation: BFS optimises the number of edges, and that is the right objective only when every edge is worth the same.

Turn diagonals off and every move costs $1$. Now BFS is genuinely optimal, and the readout shows its path cost matching the best possible exactly.

What it costs to be sure

Look at the cells examined against the count Dijkstra needed.

BFS is not paying for a better answer. It is paying because it has no way to tell a promising direction from a hopeless one, so it must examine essentially every cell closer than the goal before it can claim the goal is at the distance it thinks. Being certain of the shortest path means eliminating every shorter one.

That is the specific ignorance A* removes. A heuristic is a way of guessing which cells are worth examining first, and the shaded region collapses from a disc toward a corridor. The A* tool shows the same board with that guess switched on.

Where BFS is the right answer

On an unweighted graph BFS is optimal, complete, and hard to get wrong. It runs in $O(V + E)$ and needs no priority queue, no heuristic, and no floating-point arithmetic.

For grid navigation where every move is one move, that is often the whole job. For anything with real costs, terrain, or a large space, the queue becomes a liability rather than a virtue: it will find the shortest route while examining everything nearer than the destination, and there are far more of those cells than of useful ones.

The code

The same search in C++, with the one line that makes the first route found the shortest one:

struct Grid {
    int width, height;
    std::vector<char> wall;      // wall[y * width + x]

    bool open(int x, int y) const {
        return x >= 0 && y >= 0 && x < width && y < height && !wall[y * width + x];
    }
};

// Neighbours, with no costs attached. A* wants to know what a step is
// worth; BFS counts steps and never asks. That omission is the whole of
// why it is shortest in moves and not in distance.
//
// A diagonal is only legal when both straight moves bracketing it are
// clear, so a path never clips the corner of an obstacle.
std::vector<int> neighbours(const Grid& grid, int index, bool diagonals) {
    static constexpr int kStraightDirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static constexpr int kDiagonalDirs[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

    const int x = index % grid.width, y = index / grid.width;
    std::vector<int> out;

    for (const auto& d : kStraightDirs) {
        const int nx = x + d[0], ny = y + d[1];
        if (grid.open(nx, ny)) out.push_back(ny * grid.width + nx);
    }
    if (!diagonals) return out;

    for (const auto& d : kDiagonalDirs) {
        const int nx = x + d[0], ny = y + d[1];
        if (!grid.open(nx, ny)) continue;
        if (!grid.open(nx, y) || !grid.open(x, ny)) continue;
        out.push_back(ny * grid.width + nx);
    }
    return out;
}

std::vector<int> bfs(const Grid& grid, int start, int goal, bool diagonals = true) {
    const int count = grid.width * grid.height;
    if (!grid.open(start % grid.width, start / grid.width)) return {};
    if (!grid.open(goal % grid.width, goal / grid.width)) return {};

    std::vector<int> cameFrom(count, -1);   // the parent map, and the answer
    std::vector<char> seen(count, 0);

    // A deque, so either end can be read. Take from the front here;
    // swap that for the back and the algorithm becomes depth-first,
    // with nothing else changed.
    std::deque<int> pending{start};
    seen[start] = 1;

    while (!pending.empty()) {
        const int current = pending.front();   // the one line
        pending.pop_front();

        if (current == goal) {
            // cameFrom holds one parent per cell, so walking back from
            // the goal yields the route in reverse.
            std::vector<int> path;
            for (int at = goal; at != -1; at = cameFrom[at]) path.push_back(at);
            std::reverse(path.begin(), path.end());
            return path;
        }

        for (const int next : neighbours(grid, current, diagonals)) {
            if (seen[next]) continue;

            // Marked on discovery, not on expansion. Marking here means
            // the parent recorded for a cell is the first one to reach
            // it, and the first to reach it is the shallowest, so no
            // later route can improve on it. Mark on pop instead and a
            // cell enters the queue once per neighbour that sees it.
            seen[next] = 1;
            cameFrom[next] = current;
            pending.push_back(next);
        }
    }

    return {};   // no route
}