Searching a grid

How the four classic searches explore space, and what 'shortest path' really means. · 11 min read

Concept

A maze is just a graph in disguise: each open cell is a node, and neighbouring cells are connected by edges. Finding your way out is a graph search. The four classics all share one loop — take a node from the frontier, mark it visited, add its neighbours — and differ only in which node they take next.

• BFS takes the oldest node first (a queue) → explores in rings → shortest path on an unweighted grid.
• DFS takes the newest first (a stack) → plunges down one corridor → finds a path, not the shortest.
• Dijkstra takes the cheapest-so-far → shortest path when steps have different costs.
• A\ takes cheapest-so-far plus a guess of distance to the goal* → heads straight for the target, exploring far less.

The graph model

A graph is G = (V, E): a set of vertices and edges. In a grid, each open cell is a vertex and each legal move to a neighbour is an edge. If all edges have cost 1, the path length is just the number of steps. If edges have weights, the path cost is the sum of weights.

Unweighted shortest paths

A graph is unweighted when every edge has the same cost. In that world, the cheapest path is the path with the fewest edges. BFS is designed exactly for that: it explores all nodes at distance 0, then all nodes at distance 1, then distance 2, and so on.

DFS does not move by distance layers. It follows one branch deeply, then backtracks. That makes DFS excellent for reachability and structure discovery, but the first path it finds can be much longer than the shortest path.

Interactive visualization: BFS simulation: layer expansion — step through it frame by frame on this page.

Interactive visualization: DFS simulation: depth-first wandering — step through it frame by frame on this page.

Why BFS is shortest on unweighted graphs

BFS example

Imagine the start cell as distance 0. Its neighbours are distance 1, their unseen neighbours are distance 2, and so on. BFS processes the entire distance-k ring before touching distance k+1. So if the goal is first reached at distance 6, there cannot be a hidden distance-4 path still waiting: all distance-4 nodes were processed earlier.

queue<int> q;
vector<int> dist(n, -1);

q.push(start);
dist[start] = 0;

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

DFS is exploration, not optimization

DFS is useful when you need to visit reachable states, detect cycles, topologically sort, or search a huge space with low memory. But DFS commits to one branch before trying alternatives, so the first path it finds can be arbitrarily longer than the shortest path.

DFS notes

DFS is the right mental model for reachability, connected components, cycle detection, topological sorting, and backtracking. It can be recursive or stack-based:

void dfs(int u) {
    seen[u] = true;
    for (int v : adj[u]) {
        if (!seen[v]) dfs(v);
    }
}

Recursive DFS uses call-stack space equal to the deepest path. On a graph shaped like a chain, that is O(V) stack space.

Complexity and space

With adjacency lists, BFS and DFS both take O(V+E) time: each vertex is discovered once, and each edge is inspected a constant number of times. BFS uses O(V) space for the visited set plus queue. DFS uses O(V) visited space and either O(V) explicit stack space or recursion stack in the worst case.

Practice: Number of Islands (Easy) — Count connected groups of land in a grid.

Practice: Shortest Path in a Grid (Medium) — Fewest cells from top-left to bottom-right (BFS finds it).

Practice: Rotting Oranges (Hard) — Multi-source BFS: how long until every fresh orange rots?