Depth-first search

August 4, 2026

Depth-first search differs from breadth-first in one line of code. Instead of taking the oldest discovered cell, it takes the newest.

Click anywhere to move the goal.

The path is usually much longer than it needs to be, and the examined region is a snake rather than a disc.

One substitution

Both searches keep a list of discovered cells and repeat: take one, look at its neighbours, add the new ones.

Breadth-first takes from the front. Depth-first takes from the back.

breadth-first    pending.shift()    queue, first in first out
depth-first      pending.pop()      stack, last in first out

Everything else in the two implementations here is identical. That single choice decides the order of the search, the shape of the region it examines, the length of the path it returns, and whether it can promise anything about that path.

Why it wanders

A stack always hands back the most recently discovered cell, which is a neighbour of the cell just examined. So the search keeps walking from where it already is, and only backtracks when it reaches a dead end.

The readout compares the moves it took against the fewest that were available. The gap is usually large, and it is not bad luck. The first route DFS finds is whatever route it happened to be on when it arrived, and no property of following one direction to its end makes that route short.

Watch the cells-examined figure as you move the goal. Sometimes it is well under what Dijkstra needed, sometimes well over. DFS stops the moment it stumbles into the goal, so how much work it does depends entirely on whether the direction it committed to happened to point the right way. That is not efficiency, it is variance.

What it does guarantee

DFS is complete on a finite graph. If a route exists it will find one, because it cannot stop until every reachable cell has been examined.

It just will not tell you anything about quality. There is no ordering by distance, no ordering by cost, and no argument available that the route it returns resembles the best one.

Why it exists

Memory. BFS holds an entire frontier, which on a grid grows with the perimeter of the searched region. DFS holds one path plus the branches it has not tried, which grows with depth.

On problems where the search tree is deep and wide, that difference decides whether the algorithm runs at all. This is why DFS underlies constraint solvers, topological sorting, cycle detection, and puzzle search: those problems ask whether a solution exists, or want any consistent assignment, and the shortest route is not a meaningful question.

Iterative deepening exists for the case where you want BFS’s answer with DFS’s memory: run DFS to depth 1, then depth 2, and so on. The repeated work is smaller than it looks, because the last level of a branching tree holds most of the nodes.

Reading the three together

The same board, three orderings of the same pending list:

• Depth-first takes the newest cell. Finds a route, promises nothing.
• Breadth-first takes the oldest. Finds the fewest moves, examines nearly everything nearer.
• A* takes the most promising by $f = g + h$. Finds the cheapest route, examines a fraction of the board.

None of them is cleverer than the others internally. They differ in which end of the list they read from, and in whether they have any information about where they are going.

The code

The same search in C++, with that one line sitting where it actually sits:

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; depth-first does not even compare routes, so it has no use for
// one at all.
//
// 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> dfs(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);

    // The same deque breadth-first uses. Take from the back here; swap
    // that for the front and the algorithm becomes breadth-first, with
    // nothing else changed.
    std::deque<int> pending{start};
    seen[start] = 1;

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

        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)) {
            // Marking on discovery rather than on expansion is what keeps
            // a cell from entering the pending list twice.
            if (seen[next]) continue;
            seen[next] = 1;
            cameFrom[next] = current;
            pending.push_back(next);
        }
    }

    return {};   // no route
}