Depth-First Search (DFS)

Depth-first search (DFS) is a fundamental algorithm for traversing or searching a tree or graph: it explores as far as possible down one path before backtracking to try another. Whenever you need to visit every reachable node, detect cycles, find connected components, or explore all possibilities in a search space (mazes, puzzles, backtracking problems), DFS is usually the first tool you reach for. It sits alongside breadth-first search (BFS) as one of the two core graph traversal strategies, and understanding it deeply pays off across dozens of interview and real-world problems.

Overview: How Depth-First Search Works

Picture a graph of six rooms connected by hallways: A connects to B and C; B connects to A, D, and E; C connects to A and F; and E connects to F. If you start at A and use a depth-first strategy, you don’t check all of A‘s neighbors first before moving on. Instead you pick one neighbor, say B, and immediately dive into B‘s neighbors, then D‘s, continuing down and down until you hit a dead end – a node with no unvisited neighbors. Only then do you backtrack to the most recent node that still has an unvisited neighbor left, and continue from there. This backtrack-when-stuck behavior is what makes it ‘depth’-first: you commit fully to one path before trying alternatives, unlike BFS, which explores level by level outward from the start.

Two things make this work: a way to remember where to backtrack to, and a way to avoid revisiting nodes (which matters enormously once the graph has cycles – without it, DFS would loop forever bouncing between connected nodes). The ‘remember where to backtrack to’ part is naturally provided by a stack, and there are two idiomatic ways to get one in Python:

• Recursive DFS uses Python’s own call stack. Each recursive call is a new stack frame; when a call has no more unvisited neighbors to explore, it returns, and control naturally goes back (‘backtracks’) to the caller, which tries its next neighbor.
• Iterative DFS uses an explicit list as a stack, pushing neighbors with .append() and popping with .pop() (both O(1) at the end of a Python list). This avoids relying on the interpreter’s call stack, which matters because Python’s default recursion limit is around 1000 – a very deep or unluckily-shaped graph can trigger a RecursionError with the recursive version.

Either way, you need a visited set (a Python set, giving O(1) average membership checks) so you never process the same node twice. Marking a node visited the moment you first see it – not just when you finish processing it – is what prevents infinite loops on cyclic graphs.

Graphs are usually represented as an adjacency list: a dictionary mapping each node to a list of its neighbors. This is the right default for most real graphs, which tend to be sparse (relatively few edges compared to the maximum possible). An adjacency matrix (a 2D grid where matrix[i][j] is true if an edge exists) trades more memory for O(1) ‘does this edge exist’ lookups, and fits better for dense graphs or when you frequently need to check a specific edge rather than iterate all of a node’s edges.

Time and Space Complexity

DFS visits every reachable vertex once and examines every edge from that vertex once, so its complexity is expressed in terms of V (number of vertices) and E (number of edges):

Representation	Time	Space	Why
Adjacency list	O(V + E)	O(V)	Each vertex is visited once (O(V)), and each vertex’s neighbor list is scanned once in total across the whole traversal (O(E)). The visited set and the stack (explicit or call stack) each hold at most O(V) entries.
Adjacency matrix	O(V^2)	O(V) traversal state (plus O(V^2) to store the matrix itself)	For every vertex you scan an entire row of length V to find its neighbors, even if most entries are empty.

The recursive version’s space also includes the call stack itself, which grows to O(V) in the worst case – imagine a graph that is just one long chain, where the recursion goes V levels deep before any call returns. The iterative version replaces that call stack with an explicit Python list, but its peak size is still bounded by O(V). These bounds describe a single traversal starting from one node; if you need to guarantee every vertex in a possibly-disconnected graph gets visited (as in the connected-components example below), you loop over all vertices as potential starting points, but the total work across every DFS call combined is still O(V + E) because each vertex and edge is only ever processed once overall.

Examples

Example 1: Recursive DFS that records visit order

def dfs_recursive(
    graph: dict[str, list[str]],
    node: str,
    visited: set[str] | None = None,
    order: list[str] | None = None,
) -> list[str]:
    if visited is None:
        visited = set()
        order = []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order


graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(dfs_recursive(graph, "A"))

Output:

['A', 'B', 'D', 'E', 'F', 'C']

Trace through it: starting at A, we mark it visited and append it to order. Its neighbors are ["B", "C"], so we recurse into B first. From B we try its neighbors in order – A is already visited, so we skip it and recurse into D. D‘s only neighbor is B, already visited, so that branch dead-ends and we backtrack to B, which still has E left to try. From E we recurse into F (skipping B, already visited); from F we recurse into C (its other neighbor, E, is visited). C‘s neighbors (A, F) are both visited, so everything unwinds back to the original call. The final visit order, A, B, D, E, F, C, reflects that dive-deep-before-backtracking behavior – notice C is visited last even though it is a direct neighbor of A, because the algorithm fully explored the B branch first.

Example 2: The same traversal, done iteratively

def dfs_iterative(graph: dict[str, list[str]], start: str) -> list[str]:
    visited: set[str] = set()
    order: list[str] = []
    stack: list[str] = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    return order


graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(dfs_iterative(graph, "A"))

Output:

['A', 'B', 'D', 'E', 'F', 'C']

This produces the exact same order as the recursive version, but using an explicit stack list instead of the call stack. Notice the neighbors are pushed in reversed() order: since a stack pops from the end, pushing ["C", "B"] (the reverse of ["B", "C"]) means B – the first neighbor in the original adjacency list – gets popped and visited first, matching the recursive version’s behavior of trying neighbors in their listed order. If you forget the reversed() call, the iterative version still produces a valid DFS traversal (it never revisits a node or misses one), it just visits neighbors in the opposite order.

Example 3: A realistic use case – counting connected components

from collections import defaultdict


def count_connected_components(n: int, edges: list[tuple[int, int]]) -> int:
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited: set[int] = set()
    components = 0

    for node in range(n):
        if node in visited:
            continue
        components += 1
        stack = [node]
        while stack:
            current = stack.pop()
            if current in visited:
                continue
            visited.add(current)
            for neighbor in graph[current]:
                if neighbor not in visited:
                    stack.append(neighbor)

    return components


edges = [(0, 1), (1, 2), (3, 4)]
print(count_connected_components(6, edges))

Output:

3

This is DFS put to practical use. Given 6 nodes (numbered 0 to 5) and edges (0, 1), (1, 2), and (3, 4), we build an undirected adjacency list, then loop over every node from 0 to 5. Whenever we find a node that hasn’t been visited yet, that means we’ve discovered a brand-new connected component, so we increment the counter and run a DFS from that node to mark every node reachable from it as visited (so it won’t be recounted later). Node 0 starts a DFS that visits {0, 1, 2}; node 3 starts one that visits {3, 4}; node 5 has no edges at all, so it forms its own component of size one. Three separate DFS runs, three components. This ‘loop over all nodes, DFS from each unvisited one’ pattern is exactly how you’d detect connected components, check whether a graph is fully connected, or count islands in a 2D grid (treating each land cell as a node connected to its neighboring cells).

How It Works Step by Step

Let’s trace the recursive call stack by hand on the same six-room graph from Example 1, starting at A. Each line below is one stack frame, indented to show nesting, alongside the state of visited and order at that point:

dfs(A)                                  visited={A}          order=[A]
  dfs(B)   -- A's 1st neighbor          visited={A,B}        order=[A,B]
    dfs(D) -- B's 2nd nbr (A skipped)   visited={A,B,D}      order=[A,B,D]
      D's only neighbor (B) is visited -> dead end, return
    dfs(E) -- B's 3rd neighbor          visited={A,B,D,E}    order=[A,B,D,E]
      dfs(F) -- E's 2nd nbr (B skipped) visited={A,B,D,E,F}  order=[A,B,D,E,F]
        dfs(C) -- F's 1st neighbor      visited={A,B,C,D,E,F} order=[A,B,D,E,F,C]
          C's neighbors (A, F) both visited -> dead end, return
        F's other neighbor (E) visited -> return
      E fully explored -> return
    B fully explored -> return
  dfs(C)? -- C is ALREADY visited (reached via B->E->F->C), skip it
  A fully explored -> return

The key moment is at the very end: when the top-level call at A tries its second neighbor, C, it discovers C was already visited deep inside the B branch, so it skips it entirely. That’s the essence of DFS: it doesn’t process neighbors level by level like BFS would; it fully commits to and exhausts one path before even looking at a node’s other direct connections.

Common Mistakes

Mistake 1: Forgetting to track visited nodes on a cyclic graph

If a graph has a cycle and your DFS never records which nodes it has already seen, two connected nodes will call each other back and forth forever, until Python’s recursion limit is hit and a RecursionError is raised.

def dfs_broken(graph, node):
    print(node)
    for neighbor in graph[node]:
        dfs_broken(graph, neighbor)  # no visited tracking: A and B call each other forever


graph = {"A": ["B"], "B": ["A"]}
dfs_broken(graph, "A")  # RecursionError: maximum recursion depth exceeded

The fix is to always check and update a visited set before doing any work on a node, and to bail out immediately if it’s already been seen – this is the recursive equivalent of a base case:

def dfs_fixed(
    graph: dict[str, list[str]],
    node: str,
    visited: set[str] | None = None,
) -> None:
    if visited is None:
        visited = set()
    if node in visited:
        return
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        dfs_fixed(graph, neighbor, visited)


graph = {"A": ["B"], "B": ["A"]}
dfs_fixed(graph, "A")

Output:

A
B

Now A is printed and marked visited, then B is printed and marked visited, then the recursive call back into A hits the if node in visited: return guard and stops immediately instead of recursing again.

Mistake 2: Using a mutable default argument for the visited set

It’s tempting to write visited=set() or order=[] directly in the function signature so callers don’t have to pass them in. This is a classic Python trap: default argument values are created exactly once, when the function is defined – not fresh on every call – so every call that omits the argument shares the same set and list.

def dfs_collect(graph, node, visited=set(), order=[]):
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_collect(graph, neighbor, visited, order)
    return order


# First call looks correct...
print(dfs_collect(graph, "A"))
# ...but a second call reuses the SAME default set and list from the first call,
# so every node is already "visited" and this returns almost nothing new.
print(dfs_collect(graph, "A"))

The fix, used throughout this lesson’s other examples, is to default the parameters to None and create a fresh set/list inside the function body on each call:

def dfs_collect(
    graph: dict[str, list[str]],
    node: str,
    visited: set[str] | None = None,
    order: list[str] | None = None,
) -> list[str]:
    if visited is None:
        visited = set()
    if order is None:
        order = []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_collect(graph, neighbor, visited, order)
    return order

Each top-level call (one where the caller doesn’t pass visited/order) now gets its own brand-new set and list, while recursive calls still correctly share the same ones by threading them through as arguments.

Best Practices

• Default to an adjacency list (dict of lists, or collections.defaultdict(list)) unless the graph is dense or you need O(1) ‘does edge (u, v) exist’ checks, in which case an adjacency matrix or a set of edges may be a better fit.
• Prefer the iterative version with an explicit stack for graphs that could be large or deep (e.g. graphs built from real-world data, long chains, or user-supplied input), since it sidesteps Python’s ~1000-frame recursion limit entirely.
• Always mark a node visited when you first discover it (push it), not only after fully processing it – marking too late lets the same node get pushed onto the stack multiple times before it’s ever popped.
• Never use a mutable default argument (visited=set(), order=[]) for accumulator parameters in recursive helpers – default to None and initialize inside the function body.
• Use DFS when you need to explore all paths, detect cycles, do a topological sort, or find connected components; reach for BFS instead when you specifically need the shortest path in an unweighted graph, since DFS does not guarantee shortest paths.
• For very large or adversarial recursion depths, remember Python has no tail-call optimization – deep recursive DFS can genuinely exhaust the call stack, so switch to the iterative form rather than raising the recursion limit as a workaround.

Practice Exercises

1. Write a function has_path(graph: dict[str, list[str]], start: str, end: str) -> bool that uses DFS to determine whether a path exists between start and end in an undirected graph. Hint: this is nearly identical to dfs_iterative from Example 2, but you can return True the moment you pop end off the stack, and False if the stack empties without ever finding it.
2. Given a 2D grid of the characters '1' (land) and '0' (water), write a function count_islands(grid: list[list[str]]) -> int that uses DFS to count the number of islands, where an island is a group of '1's connected horizontally or vertically (not diagonally). Hint: treat each grid cell as a node whose neighbors are the cells directly above, below, left, and right of it, and reuse the ‘loop over all nodes, DFS from each unvisited one’ pattern from Example 3.
3. Write a function has_cycle(graph: dict[int, list[int]], n: int) -> bool that detects whether an undirected graph with nodes 0 through n - 1 contains a cycle, using DFS. Hint: while exploring from a node, if you encounter a neighbor that is already visited and is not the node you just arrived from (its ‘parent’ in the DFS), you have found a cycle.

Summary

• Depth-first search fully explores one path before backtracking to try the next, using either Python’s call stack (recursive DFS) or an explicit list-as-stack (iterative DFS).
• A visited set is required to avoid infinite loops on cyclic graphs, and marking a node visited as soon as it’s discovered (not after processing) avoids duplicate work.
• Time complexity is O(V + E) with an adjacency list (every vertex and every edge is processed exactly once) versus O(V^2) with an adjacency matrix (every vertex scans a full row).
• Space complexity is O(V) for the visited set plus the stack (explicit or the recursive call stack), which can reach O(V) deep in the worst case such as a long chain graph.
• Common bugs: forgetting to check visited before recursing (infinite recursion / RecursionError on cycles), and using a mutable default argument (visited=set()) that gets silently shared and reused across separate top-level calls.
• Use DFS for reachability, cycle detection, connected components, and topological sort; use BFS instead when you specifically need shortest paths in an unweighted graph.