Depth-First Search
Explore as deep as possible before backtracking.
How it works
DFS uses a stack (LIFO) to always explore the most recently discovered node first. It dives deep into one branch of the graph before coming back to explore alternatives — like following a hallway until you hit a dead end, then backtracking to the last junction.
Unlike BFS, DFS does not guarantee a shortest path. It finds *a* path, which may be longer than optimal. The advantage is that DFS uses O(h) space where h is the depth, which is better than BFS's O(w) where w is the width of the search frontier — useful for very wide graphs.
DFS is the foundation of many graph algorithms: topological sort, cycle detection, and strongly connected components all rely on it.
Complexity
Visualizer
Where it's used in the real world
Compilers / build systems
Topological sort of dependenciesWhen compiling a project, the compiler needs to process dependencies before the files that depend on them. DFS on the dependency graph (detecting cycles and recording finish times) produces a valid build order.
Git
Reachability and merge-base computationgit log, git merge, and git cherry-pick all walk the commit DAG using DFS to find common ancestors, reachable commits, or divergence points.
Solvers (Sudoku, N-Queens, SAT)
Backtracking searchConstraint satisfaction problems use recursive DFS with backtracking. Try a value, go deep, if you hit a contradiction, pop back and try the next value.
File systems
Directory traversal (find, du, cp -r)Unix tools like find and du traverse directory trees depth-first — they go all the way into a subdirectory before moving on to the next sibling at the same level.
Implementation
// Iterative DFS using explicit stack
function dfs(graph: Map<string, string[]>, start: string, end: string): string[] | null {
const stack: string[] = [start];
const visited = new Set<string>();
const parent = new Map<string, string | null>([[start, null]]);
while (stack.length > 0) {
const node = stack.pop()!; // LIFO — pop from top
if (visited.has(node)) continue;
visited.add(node);
if (node === end) {
// Reconstruct path
const path: string[] = [];
let cur: string | null = end;
while (cur !== null) {
path.unshift(cur);
cur = parent.get(cur) ?? null;
}
return path;
}
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
if (!parent.has(neighbor)) parent.set(neighbor, node);
stack.push(neighbor);
}
}
}
return null; // no path
}