The core idea: commit to a path, then backtrack
Imagine exploring a maze by always taking the first unexplored corridor you see and only turning back when you hit a dead end. That is depth-first search. Instead of fanning out evenly, DFS commits fully to one path, following it as deep as it goes, then retreats to the last junction that still has an untried option and dives again.
That single behavior — go deep, backtrack, repeat — is what makes DFS feel natural to write with recursion. Each recursive call is one step deeper; each return is one backtrack. Because it reveals the structure one edge at a time, DFS is easy to picture when you watch it animate step by step.
How it works: recursion, an explicit stack, and visited state
DFS needs three things: a way to reach neighbors, a way to remember where it has been, and a way to backtrack. You visit a node, mark it visited, then recurse into each unvisited neighbor — the call stack does the remembering and backtracking for you. Swap the recursion for an explicit stack and you get the iterative version: push a start node, then repeatedly pop, visit, and push unvisited neighbors.
The visited set is not optional on graphs. Without it, any cycle sends DFS into an infinite loop, and even in an acyclic graph you would re-explore shared nodes wastefully. On a tree there are no cycles, so you can skip the visited set — remembering the parent is enough to avoid walking back up. The order in which you push neighbors decides which branch you explore first, so DFS output is not unique unless that order is fixed.
What DFS unlocks: cycle detection, components, topological sort
DFS is a workhorse because its backtracking structure exposes useful facts almost for free. Track which nodes are currently on the recursion stack and you can detect a cycle the instant you meet a node that is still 'in progress' — the basis of deadlock and dependency-loop checks. Run DFS from every unvisited node and count how many times you have to start fresh: that count is the number of connected components.
Topological sort falls out of the same traversal. Run DFS and record each node the moment its recursion finishes; reverse that finish order and you get a valid ordering where every edge points forward — exactly what you need to schedule tasks with prerequisites or resolve build dependencies. These payoffs are why DFS appears far more often than its one-line definition suggests.
def dfs(graph, start):
"""Recursive DFS returning nodes in visit order."""
visited, order = set(), []
def explore(node):
visited.add(node)
order.append(node)
for neighbor in graph[node]: # graph: {node: [neighbors]}
if neighbor not in visited:
explore(neighbor)
explore(start)
return order
def dfs_iterative(graph, start):
"""Same traversal using an explicit stack instead of recursion."""
visited, order, stack = set(), [], [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
stack.extend(n for n in graph[node] if n not in visited)
return orderUsing an adjacency list, DFS touches every vertex and edge once, giving O(V + E); an adjacency matrix raises this to O(V²). Time does not vary by case since DFS visits the whole reachable structure. Space is O(V) for the visited marks plus the recursion or explicit stack, whose depth reaches O(V) in the worst case (a single long path) and is shallower on bushy graphs or balanced trees.
When to use it
- Detecting cycles in a directed graph — for example, circular dependencies in a build system, package manager, or import graph.
- Producing a topological order for tasks with prerequisites, like course scheduling or a job pipeline.
- Counting or labeling connected components and flood-fill regions in a grid or network (the classic 'number of islands' problem).
- Exhaustively exploring all paths or configurations — the backbone of backtracking problems like maze solving, N-Queens, and generating permutations.
Watch out for
- Forgetting the visited set on a cyclic graph, which turns DFS into an infinite loop — or causes wasteful re-exploration of shared nodes even when there are no cycles.
- Hitting a stack overflow from deep recursion on large graphs; convert to an explicit stack or raise the recursion limit when chains can be very long.
- Confusing 'visited' with 'currently on the recursion stack' for cycle detection — directed-graph cycles need a separate in-progress state (three-color marking), not just a single visited flag.
DFS is one of the highest-frequency patterns in coding interviews, and it rarely shows up by name — it hides inside problems like 'number of islands,' 'course schedule,' 'clone graph,' and 'word search.' Interviewers want to see that you recognize a problem as a graph or grid traversal, that you handle the visited set correctly to avoid infinite loops, and that you can state the O(V + E) complexity confidently. Strong bonus signals include switching between the recursive and iterative forms on request, using three-color marking to detect cycles in a directed graph, and knowing when DFS is the wrong tool — for the shortest path in an unweighted graph, BFS is the answer they are listening for.