Depth-first search

Depth-first search, or DFS, explores a graph by following one path as far as it can go, then backing up to the most recent fork and trying the next branch. It’s naturally written with recursion or an explicit stack. The order in which DFS enters and finishes nodes reveals structure: if it reaches a node that’s still on the current path, the graph has a cycle, and listing nodes in reverse order of when they finish gives a topological order, a sequence where every dependency comes before what depends on it. That’s how build systems and package managers decide what to do first. DFS also finds connected components and drives most backtracking.