Depth-first search
Overview
Depth-first search (DFS) follows unvisited neighbors down a single branch until it reaches a dead end, then backtracks to the most recent junction to try the next branch. Like opening nested subdirectories all the way down before moving to the next sibling folder, the search remembers where it paused at each junction so it can resume cleanly on return.
History
Backtracking from dead ends to the last unfinished junction dates back to Charles Pierre Trémaux’s 19th-century maze-solving rules, recounted by Édouard Lucas in *Récréations Mathématiques* in 1882.1 In 1971–1972, John Hopcroft and Robert Tarjan formalized the structure of DFS spanning trees (palm trees) and back edges; Tarjan’s 1972 paper “Depth-First Search and Linear Graph Algorithms” showed how this traversal order yields linear-time algorithms for strongly connected and biconnected components.2
Explicit stack frames and the parenthesis theorem
In recursive DFS, the language call stack records the active vertex and which neighbor to inspect next, but a deep path of tens of thousands of vertices can overflow the call stack (RangeError: Maximum call stack size exceeded). The implementation below stores { vertex, next } frames in a heap-allocated array, avoiding call-stack overflow while reproducing the exact discovery order of recursive DFS.
A common naive iterative variant pops a vertex and pushes all of its unvisited neighbors at once; that reverses neighbor order and can push duplicate pending vertices, inflating stack space to . Advancing next one child at a time keeps only the current ancestor chain on the stack. If records when vertex is pushed and records when it is popped, the active intervals obey the parenthesis theorem:
Executable example
Running DFS on the same directed graph used in Breadth-first search highlights where their orders diverge: after stepping from A to B, DFS continues down to D before ever visiting C. The seen array prevents cycles from re-entering discovered vertices.
function depthFirst(graph: readonly (readonly number[])[], start: number): number[] {
const seen = new Array<boolean>(graph.length).fill(false);
const order = [start];
// Store the next neighbor index in each frame to resume exactly where recursion would.
const stack = [{ vertex: start, next: 0 }];
seen[start] = true;
while (stack.length > 0) {
const frame = stack[stack.length - 1]!;
const neighbors = graph[frame.vertex]!;
if (frame.next === neighbors.length) {
stack.pop();
continue;
}
const to = neighbors[frame.next++]!;
if (seen[to]) continue;
seen[to] = true;
order.push(to);
stack.push({ vertex: to, next: 0 });
}
return order;
}
const names = ['A', 'B', 'C', 'D', 'E'];
const graph = [[1, 2], [3], [3, 4], [], []];
console.log(depthFirst(graph, 0).map(index => names[index]).join(','));Output:
A,B,D,C,EWhen B finishes and control returns to A, the search advances to C, skips D because seen[3] is already true, and visits E. Keeping next inside each frame lets the parent resume at its next unread neighbor without rescanning earlier neighbors.
C++ example
In C++, default thread stack limits (typically 1–8 MiB) can still overflow on deep graphs with hundreds of thousands of vertices. Storing Frame{vertex, next} in a std::vector<Frame> keeps the active chain on the heap; re-fetching stack.back() on each iteration avoids dangling references across push_back reallocations.
#include <cstddef>
#include <iostream>
#include <vector>
struct Frame {
int vertex;
std::size_t next;
};
std::vector<int> depthFirst(const std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> seen(graph.size(), false);
std::vector<int> order{start};
// Store the next neighbor index in each frame to resume where recursion would.
std::vector<Frame> stack{{start, 0}};
seen[start] = true;
while (!stack.empty()) {
Frame& frame = stack.back();
const auto& neighbors = graph[frame.vertex];
if (frame.next == neighbors.size()) {
stack.pop_back();
continue;
}
int to = neighbors[frame.next++];
if (seen[to]) continue;
seen[to] = true;
order.push_back(to);
stack.push_back({to, 0});
}
return order;
}
int main() {
const char names[] = {'A', 'B', 'C', 'D', 'E'};
const std::vector<std::vector<int>> graph{{1, 2}, {3}, {3, 4}, {}, {}};
const auto order = depthFirst(graph, 0);
for (std::size_t i = 0; i < order.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << names[order[i]];
}
std::cout << '\n';
return 0;
}Output:
A,B,D,C,ECost and scope
For vertices and adjacency entries, each vertex is pushed at most once and its next counter increments once per outgoing edge, giving time. Because the stack holds at most one frame per discovered vertex on the active path, auxiliary space is .
While DFS does not find shortest hop counts, its discovery and finish intervals drive topological sorting (by reverse finish order), cycle detection (via edges pointing to vertices currently on the active stack), and linear-time decomposition into strongly connected or biconnected components.