Depth-First Search

Depth-first search (DFS) is a graph search algorithm that explores as far as possible along each branch before backtracking, using a stack to track the current path. Unlike breadth-first search, which prioritizes coverage, DFS prioritizes depth — making it memory-efficient (requiring only storage for the current path) but incomplete in infinite spaces and non-optimal for shortest-path problems.

DFS is not merely a graph algorithm; it is a model of how systems explore when they have limited memory and no global map. In game tree search, it corresponds to speculative play that commits to a line of reasoning before considering alternatives. In maze solving, it is the strategy of hugging a wall and backtracking only when a dead end is reached. The algorithm's radical simplicity — it needs only a stack and a visited set — makes it the computational analog of trial-and-error exploration in biological and social systems.