DFS Traversal Template
Depth-first search visits a node, then recursively visits each unvisited neighbor before backtracking. It is the natural traversal for tree problems, cycle detection, topological order, and connected-components. This snippet covers the recursive form, an iterative stack-based form for very deep graphs, and a path-tracking variant that surfaces the actual route from start to a target.
180 views
5
function dfs(start, getNeighbors) {
const visited = new Set();
const order = [];
function visit(node) {
if (visited.has(node)) return;
visited.add(node);
order.push(node);
for (const next of getNeighbors(node)) visit(next);
}
visit(start);
return order;
}
const graph = { A: ['B', 'C'], B: ['D'], C: ['D', 'E'], D: [], E: [] };
console.log(dfs('A', (n) => graph[n])); // [A, B, D, C, E]Recursive DFS uses the call stack as the implicit traversal stack. The visited set prevents cycles from causing infinite recursion, and pushing onto the order list at visit-time produces a pre-order traversal. The recursion depth is the length of the longest path from start, which matters for very deep graphs (V8's default stack supports ~10000 frames). For small to moderate graphs this is the cleanest implementation; for huge ones see the iterative form in the next accordion.
function dfsIterative(start, getNeighbors) {
const visited = new Set();
const stack = [start];
const order = [];
while (stack.length > 0) {
const node = stack.pop();
if (visited.has(node)) continue;
visited.add(node);
order.push(node);
const neighbors = getNeighbors(node);
for (let i = neighbors.length - 1; i >= 0; i--) {
if (!visited.has(neighbors[i])) stack.push(neighbors[i]);
}
}
return order;
}
const g = { A: ['B', 'C'], B: ['D'], C: ['D', 'E'], D: [], E: [] };
console.log(dfsIterative('A', (n) => g[n])); // [A, B, D, C, E]Replacing recursion with an explicit stack moves the work onto the heap, which removes the call-stack-overflow risk on pathological inputs (a million-node linked-list graph, for example). Pushing neighbors in reverse order is the trick that makes the iterative output match the recursive pre-order: pop() returns the most recent push, so the first child must be pushed last. This same skeleton powers iterative tree traversals when implementing them recursively would blow the stack.
function findPath(start, target, getNeighbors) {
const visited = new Set();
function visit(node, path) {
if (node === target) return path;
visited.add(node);
for (const next of getNeighbors(node)) {
if (visited.has(next)) continue;
const result = visit(next, [...path, next]);
if (result !== null) return result;
}
return null;
}
return visit(start, [start]);
}
const graph2 = { A: ['B', 'C'], B: ['D'], C: ['E'], D: [], E: ['F'], F: [] };
console.log(findPath('A', 'F', (n) => graph2[n])); // [A, C, E, F]
console.log(findPath('A', 'Z', (n) => graph2[n])); // nullSometimes the goal is not just reachability but the actual sequence of nodes. Threading the path as a function argument lets each branch own its prefix, and returning the path the moment we reach the target produces an exit early without unwinding manually. The path is O(depth) extra memory per branch, and the algorithm is still O(V + E) overall because visited prevents revisits. Note this returns ANY path, not the shortest; use BFS for shortest paths in unweighted graphs.