Take breadth-first search and swap its queue for a stack and the skeleton barely changes — visit a node, push its unvisited neighbors, repeat — but the behavior is opposite. A queue hands back what it received earliest; a stack hands back what it received most recently. So instead of fanning out one distance-layer at a time, depth-first search commits to a single neighbor, then that neighbor's neighbor, diving as deep as the maze allows before it ever backs up to try a different branch. It still visits every reachable node — but it gives up BFS's shortest-path guarantee to do it.
Same maze shape as the BFS page, same click-to-toggle walls, but watch the stack below the grid instead of a queue: the current cell being popped gets a bold border, cells it discovers get pushed onto the top (right end, highlighted), and the next pop always comes from that same end. Compare the wandering path this finds against BFS's straight-line shortest path on the same layout.
The stack is the whole mechanism, same as the queue was for BFS — only the discipline for which cell comes out next differs. Because the stack is LIFO, the moment DFS discovers a new cell it immediately dives into it on the very next pop, before any of the sibling cells sitting underneath it on the stack get a turn. That's what "depth-first" means literally: go deep before going wide. There's no guarantee the first path found is the shortest — DFS might wander down a long dead-end branch, back all the way up, and only then stumble onto the direct route — but it's guaranteed to eventually visit every cell reachable from the start, because nothing is ever skipped, just deferred.
Iterative version with an explicit stack, matching the demo above. Unlike the BFS reference — which marks a cell visited the moment it's enqueued — this marks visited on pop, which means the same cell can sit on the stack more than once before it's finally processed (see Pitfalls):
function dfs(grid, rows, cols, start, end) {
const key = (r, c) => r * cols + c;
const visited = new Array(rows * cols).fill(false);
const parent = new Array(rows * cols).fill(-1);
const stack = [{ node: key(...start), parent: -1 }];
const endKey = key(...end);
let foundKey = -1;
while (stack.length > 0) {
const { node: cur, parent: par } = stack.pop();
if (visited[cur]) continue; // already handled via an earlier push
visited[cur] = true;
parent[cur] = par;
if (cur === endKey) { foundKey = cur; break; }
const r = Math.floor(cur / cols), c = cur % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nk = nr * cols + nc;
if (visited[nk] || grid[nk] === WALL) continue;
stack.push({ node: nk, parent: cur });
}
}
if (foundKey === -1) return null; // unreachable
const path = [];
for (let cur = foundKey; cur !== -1; cur = parent[cur]) path.push(cur);
return path.reverse();
}The far more common way to write DFS is recursively, letting the language's own call stack
play the role of the explicit stack array above:
function dfsRecursive(grid, rows, cols, cur, end, visited, parent) {
visited[cur] = true;
if (cur === end) return true;
const r = Math.floor(cur / cols), c = cur % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nk = nr * cols + nc;
if (visited[nk] || grid[nk] === WALL) continue;
parent[nk] = cur;
if (dfsRecursive(grid, rows, cols, nk, end, visited, parent)) return true;
}
return false;
}Both traverse cells in the same order and visit the same set — the recursive version just
never allocates a stack array, because every recursive call is a push and
every return is a pop.
Marking visited on pop instead of push. BFS marks a cell visited the instant
it's enqueued, which guarantees each cell appears in the queue at most once. The DFS
reference above marks on pop instead, so the same cell can be pushed by more than one
still-unprocessed neighbor before any of those pushes are popped — the if (visited[cur])
continue line is what discards the stale duplicates once one of them finally wins. This is
harmless for correctness and is how most iterative DFS implementations are written, but it does
mean the stack can briefly hold more entries than the queue would for the equivalent BFS — worth
knowing if you're reasoning about peak memory.
No shortest-path guarantee. The demo above makes this concrete: run it on the default maze and DFS's path is dramatically longer than the straight route BFS finds on the exact same layout, because DFS commits to whichever neighbor it tries first and only backs out after exhausting that entire branch. If you need the shortest path in an unweighted graph, BFS is the right tool; DFS answers a different question — "is anything reachable, and what does one path look like" — not "what's the shortest path."
Recursive DFS can overflow the call stack. The recursive version above is elegant, but on a graph with a long deep chain (a linked-list-shaped graph, or an unlucky maze) the recursion depth can exceed the language's call-stack limit and crash with a stack overflow — the same overflow pitfall that applies to any runaway recursion. The iterative version with an explicit array-backed stack has no such limit (short of running out of heap memory), which is the main practical reason to reach for it on large or untrusted graphs.
This maze is undirected, but DFS on a directed graph unlocks two more classic uses. Track which nodes are still "on the current path" versus fully finished (not just visited-or-not) and DFS can detect a cycle — an edge back to a node that's still on the path means one exists. Push each node onto a stack the moment it finishes, then reverse that stack at the end, and you get a topological sort: a valid ordering where every edge points from something earlier to something later. Both are the same traversal as this maze, just with directed edges and one extra bit of bookkeeping per node.
Time: O(V + E) — every vertex is popped and marked visited
exactly once, and every edge is inspected once (twice, from each endpoint, on an undirected graph
like this grid). On an r × c grid this is O(r·c), identical to BFS.
Space: O(V) for the visited array, the parent array, and the stack —
which, because of the mark-on-pop duplicates above, can in the worst case hold more than V
entries at once, though it's still bounded by O(E).
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.