What is DFS

Depth-first search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It follows one path until it hits a dead end (a node with no unvisited neighbors), then backs up and tries the next branch. DFS uses a stack — either the call stack via recursion or an explicit stack data structure.

How it works

The recursive version is concise:

1. Mark the current node as visited.
2. For each unvisited neighbor, recurse.
3. When all neighbors have been visited, return (backtrack).

Graph:   A — B — E
         |   |
         C — D — F

DFS from A (choosing neighbors left to right):
  Visit A → Visit B → Visit D → Visit C (already visited via A, skip)
                                 Visit F → backtrack
                       backtrack
              Visit E → backtrack
         backtrack
  Visit C (already visited, skip)

Visit order: A, B, D, F, E, C

Unlike BFS, which explores layer by layer, DFS dives deep immediately. It does not find shortest paths — it finds a path, but not necessarily the shortest one. Its strength lies elsewhere.

The time complexity is O(V + E), the same as BFS. Every node and edge is examined once. Space complexity is O(V) for the visited set plus the stack depth, which is O(V) in the worst case (a long chain graph).

DFS is the engine behind several important graph algorithms:

• Cycle detection — if DFS encounters a node that is currently on the stack (being explored, not yet backtracked), the graph contains a cycle. This is essential for dependency resolution.
• Topological sorting — ordering nodes in a directed acyclic graph so that every edge points from earlier to later. DFS processes nodes in reverse finish order, which gives the topological order.
• Connected components — running DFS from each unvisited node finds all connected components in an undirected graph.
• Maze solving and backtracking — DFS naturally explores one path, backtracks on failure, and tries alternatives.

Why it matters

DFS is fundamental to compiler design (dependency ordering), package managers (detecting circular dependencies), maze generation, and any problem that requires exhaustive exploration. Where BFS answers "what is the shortest path?", DFS answers "is there a path?" and "is there a cycle?" Together, BFS and DFS cover the two essential strategies for exploring graphs.

See How Graph Algorithms Work for cycle detection, topological sort, and comparisons with BFS.