Depth-First Search
Go as deep as possible before backtracking. DFS is the natural traversal for connectivity, flood fill, and anything tree-shaped.
Key ideas
- —Recursion gives you DFS for free — the call stack is the explicit stack.
- —Mark visited to avoid infinite loops on graphs with cycles.
- —DFS is the backbone of flood fill, connected components, and cycle detection.
Recursion is the stack
A recursive DFS visits a node, then recurses into each unvisited neighbor, unwinding when it hits a dead end. The implicit call stack does the bookkeeping a queue would do for BFS. For grids, the four (or eight) neighbor offsets become the edges, which is why "number of islands" and flood fill are textbook DFS.
Visited sets and memoized DFS
On any graph that may contain cycles, a visited set is mandatory or you will recurse forever. When subproblems overlap — like the longest increasing path in a matrix — cache each node's result so repeated visits return instantly, turning exponential exploration into linear work.
Practice this
Sources
- Depth-first searchWikipedia
- Depth First SearchCP-Algorithms