Graph DFS

TL;DR

Depth-first search walks a graph by going as deep as possible along one branch before backtracking. Recursive form is two lines of real logic: mark the current node visited, then recurse into every unvisited neighbor. Iterative form swaps the call stack for an explicit list used as a LIFO. Either form runs in O(V + E) and uses O(V) memory for the visited set plus the stack.

DFS is the right tool when you need to enumerate something: connected components (“how many islands?”), reachability (“does a path exist from A to B?”), exhaustive search over a board (word search, Sudoku), cycle detection, or topological order on a DAG. The traversal order doesn’t matter for correctness — you only need every reachable node visited exactly once.

DFS is the wrong tool when distance matters. Shortest path on an unweighted graph is BFS, not DFS, because DFS will happily walk a long path to a neighbor that BFS would have reached in one step. If the question mentions “minimum number of steps”, “fewest moves”, or “shortest”, stop and reach for BFS instead.

The three flavors below — grid DFS, adjacency-list DFS, and boundary DFS — cover roughly 90% of LeetCode graph problems and most production uses.

When to reach for it

Strong signals that DFS is the right pattern:

• Count regions / components. “Number of islands”, “number of provinces”, “count connected friend groups”. Each outer loop start that finds an unvisited node is one component.
• Cycle detection. Directed cycle on a dependency graph (compile order, package resolver), or undirected cycle via a parent check.
• Flood / fill. Paint bucket, “make all ‘O’s surrounded by ‘X’ into ‘X’”, “color this region”.
• Exhaustive board search. Word search on a grid, Sudoku, N-queens — anywhere you place a candidate, recurse, and undo on failure (DFS + backtracking).
• “Does a path exist that satisfies …” — any reachability question where you don’t care about path length, only existence.

If the question is “shortest”, “minimum steps”, or “level by level”, it’s BFS. If you need both reachability and distance, it’s still BFS.

Flavor 1 — grid DFS (number of islands, max area)

Treat each cell as a node, with edges to its 4 orthogonal neighbors. A component is an “island” of 1s surrounded by 0s.

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"  # mark visited in place
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)
    return count

Worked example. A 3x4 grid:

1 1 0 0
1 0 0 1
0 0 1 1

Outer loop scans row-major. The first 1 at (0,0) triggers a DFS that eats the entire top-left island. The next unvisited 1 is at (1,3), which kicks off the second component.

Final count: 2. Note we mutated the grid as our visited marker — no separate set needed. For “max area of island”, change dfs to return 1 + sum(dfs(...) for each direction) and track the max.

Flavor 2 — adjacency-list DFS for components & cycles

Most non-grid graphs come as dict[int, list[int]] or as an edge list you convert. The template uses an explicit visited set.

def connected_components(n: int, edges: list[tuple[int, int]]) -> int:
    adj: dict[int, list[int]] = {i: [] for i in range(n)}
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = set()

    def dfs(node: int) -> None:
        visited.add(node)
        for nxt in adj[node]:
            if nxt not in visited:
                dfs(nxt)

    components = 0
    for node in range(n):
        if node not in visited:
            components += 1
            dfs(node)
    return components

Cycle detection on a directed graph needs a 3-color trick: white (unvisited), gray (on the current DFS path), black (fully explored). A gray neighbor means a back-edge, which means a cycle.

def has_cycle(n: int, adj: dict[int, list[int]]) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(u: int) -> bool:
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                return True              # back-edge → cycle
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(color[u] == WHITE and dfs(u) for u in range(n))

Trace 0 -> 1 -> 2 -> 0: DFS from 0 colors 0 gray, recurses to 1 (gray), to 2 (gray). 2’s neighbor 0 is already gray → cycle.

For an undirected graph, replace the gray check with “neighbor visited and neighbor != parent” — otherwise the edge you just walked counts as a cycle of length 2.

Flavor 3 — boundary DFS (Pacific Atlantic, Surrounded Regions)

Some problems look like “for every cell, ask whether it can reach X”. The naive solution runs DFS from every cell — O((rows·cols)²). The trick: invert the question. DFS from the cells you already know the answer for, and let it flood inward.

def pacific_atlantic(heights: list[list[int]]) -> list[tuple[int, int]]:
    if not heights:
        return []
    rows, cols = len(heights), len(heights[0])
    pac, atl = set(), set()

    def dfs(r: int, c: int, seen: set, prev: int) -> None:
        if (r, c) in seen: return
        if r < 0 or r >= rows or c < 0 or c >= cols: return
        if heights[r][c] < prev: return  # water flows downhill, we're walking up
        seen.add((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            dfs(r + dr, c + dc, seen, heights[r][c])

    for c in range(cols):
        dfs(0, c, pac, heights[0][c])
        dfs(rows - 1, c, atl, heights[rows - 1][c])
    for r in range(rows):
        dfs(r, 0, pac, heights[r][0])
        dfs(r, cols - 1, atl, heights[r][cols - 1])

    return list(pac & atl)

Why boundary-in beats per-cell: the answer is “set of cells that reach the edge”. The edge cells trivially reach themselves. Water flows downhill in the problem, so we walk uphill from each ocean. Every cell gets visited at most twice (once per ocean), giving O(rows·cols) instead of O((rows·cols)²).

Surrounded Regions (LC 130) uses the same trick: any O connected to a border O is safe, so DFS from border Os, mark them, then flip every unmarked O to X.

Why it works — the invariant

DFS rests on one invariant: once a node is marked visited, it is never re-entered. The first thing the recursive function does after the bounds check is mark visited (or push to a visited set). Every recursive call re-checks before descending, so each node is the subject of at most one expansion.

That gives two guarantees. First, termination: a finite graph has a finite visited set, so recursion bottoms out. Second, the recursion stack at any moment is exactly the current DFS path from the root to the active node — this is what makes the gray/black cycle detection work, what lets backtracking restore state on the way up, and what bounds stack depth at O(V).

Complexity

• Time: O(V + E). Every vertex is expanded once; every edge is examined at most twice (undirected) or once (directed). For a grid that’s O(rows·cols) since each cell has at most 4 edges.
• Space: O(V) for the visited set plus O(V) worst case for the recursion stack (a long chain graph). On a grid, recursion depth can hit rows·cols in the pathological “snake” case — a 1000x1000 grid blows the default Python recursion limit of 1000 frames.

Common pitfalls

• Python recursion limit. Default is 1000. A 1000x1000 fully-connected island will overflow. Either sys.setrecursionlimit(10**6) (and pray for stack memory), or rewrite as iterative DFS with an explicit list used as a LIFO stack.
• Marking visited too late. If you mark visited after the recursive calls return, two neighbors will both push each other before either marks, and you’ll re-enter the same node and (best case) explode the stack, (worst case) infinite-loop. Mark visited as the first statement after bounds checks.
• Mixing in-place mutation with a separate visited set. Pick one. If you flip grid[r][c] = '0' to mark visited, don’t also maintain a visited set with stale state — they’ll disagree and you’ll double-count or skip cells.
• Off-by-one on grid bounds. r < rows, not r <= rows. Forgetting the lower bound r >= 0 is the more insidious bug — Python’s negative indexing happily wraps grid[-1] to the last row and gives you a wrong answer with no exception.
• Forgetting to undo state in backtracking. Word Search and Sudoku-style problems need to unmark the cell on the way back up, because the cell is reusable on a different path. Pure component-counting DFS does not.

Where you see this in production

• Dependency cycle detection in package resolvers. npm, cargo, and pip’s resolver all run a DFS over the dependency DAG with the white/gray/black coloring above; a back-edge raises a cycle error before the install proceeds.
• CPython garbage collector mark phase. The gc module’s cyclic collector starts from root objects and DFSes through references to mark reachable allocations; everything unmarked at the end of the sweep is freed.
• LLVM control-flow graph analysis. Passes like dead-code elimination and dominator-tree construction DFS the CFG of each function; the post-order produced by the recursion is what feeds the dominator algorithm.
• Photoshop / GIMP bucket-fill tool. The 4- or 8-connected flood-fill is exactly Flavor 1 above, with a color-tolerance check replacing the grid[r][c] == "1" test.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• William Fiset — Graph Theory playlist — www.youtube.com