Depth-first search
AlgorithmsGo as deep as possible, then backtrack — the natural fit for connectivity and ordering.
Definition
DFS explores as far as possible along each branch before backtracking, expressed with recursion or an explicit stack. It uses O(depth) stack space and naturally captures connectivity, cycle detection, and ordering — but it does not find shortest paths.
When to use
Reach for DFS for connected components, path existence, flood-fill, topological ordering, and tree traversals. On cyclic graphs you must mark visited nodes; on very deep graphs, prefer an explicit stack to avoid blowing the call stack.