Depth-First Search

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Starting from a source node it follows one path until it reaches a dead end, then backs up to the most recent branching point and tries the next unexplored edge, typically using recursion or an explicit stack.

How it works

DFS marks the start node visited, then recursively visits the first unvisited neighbor, going deeper at each step. When a node has no unvisited neighbors, the recursion unwinds and the search resumes from the previous node. Each vertex and edge is handled exactly once, giving O(V + E) time and O(V) space for the visited set and recursion stack. The order in which nodes enter and leave the recursion yields discovery and finish times used by many derived algorithms.

Applications

DFS is the foundation for topological sorting, cycle detection, strongly connected components, articulation points, bridges, and maze generation. In practice it underlies dependency resolution in build tools, deadlock detection, and puzzle solvers. Interviewers use DFS constantly in problems involving backtracking, islands in grids, and path enumeration.