Graph DFS

At a glance

The instinct

Depth-first search answers "what can I reach from here, and what does that region look like?" It walks one corridor to its end, then backs up to the last junction and tries the next corridor. The call stack remembers the junctions for you, so the code is short: mark the node, then recurse into each neighbour that is not yet marked.

Graph DFS shows up whenever the answer is about a whole component (its size, its shape, whether it touches the border), about every path from a source, or about a property that must hold along every edge (bipartite colours, cloned copies). Grids are just graphs whose neighbours are the four adjacent cells.

Recognise it

Not this pattern if...

• The question asks for the fewest steps or shortest path in an unweighted graph: use BFS.
• Edges are being added over time and you answer "are a and b connected?": Union-Find.
• You need an order that respects prerequisites: Topological Sort (which can be DFS-based, but the goal differs).
• Edges have weights and you want the cheapest path: Dijkstra.

Memory hack

Analogy: exploring a cave with chalk. You chalk an X on every chamber you enter and always take the first unchalked tunnel. When every tunnel from a chamber leads to chalk, you retrace your steps. You will see every chamber reachable from the entrance, exactly once.

Say it out loud in the interview:

1. "Nodes are ___, neighbours are ___ (grid: 4 directions with bounds check)."
2. "I mark visited on entry, then recurse into unvisited neighbours; each DFS call returns ___."
3. "I launch DFS from every unvisited node (or from the border) and combine the results."

How it works

For a grid, the outer loop scans every cell; each unvisited land cell triggers one DFS that sinks the whole island. The count of triggers is the number of islands.

flowchart TD
  S["Scan every node or cell"] --> Q{"Unvisited and valid?"}
  Q -- no --> S
  Q -- yes --> L["Launch DFS, components++"]
  L --> M["Mark node visited"]
  M --> N{"Next neighbour?"}
  N -- "in bounds, unvisited" --> M2["Recurse into neighbour"]
  M2 --> M
  N -- "none left" --> R["Return to caller, backtrack"]
  R --> S

Three useful twists:

• Reverse direction. In Pacific Atlantic Water Flow, instead of asking whether water from each cell reaches an ocean, start at each ocean's border and climb uphill. Cells marked by both searches are the answer. Surrounded Regions uses the same trick: anything connected to the border is safe.
• Colour instead of visited. For Is Graph Bipartite?, store colour 0/1; a neighbour with the same colour fails, an uncoloured neighbour gets the opposite colour.
• Map as visited. In Clone Graph, the old → copy map doubles as the visited set.

Java template

import java.util.*;

class GraphDfs {
    // Grid flood fill: returns the size of the region containing (r, c).
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    static int fill(char[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return 0;
        g[r][c] = '#';                                  // mark before exploring
        int size = 1;
        for (int[] d : DIRS) size += fill(g, r + d[0], c + d[1]);
        return size;
    }

    static int countRegions(char[][] g) {
        int count = 0;
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++)
                if (g[r][c] == '1') { fill(g, r, c); count++; }
        return count;
    }

    // Adjacency-list DFS, iterative to avoid stack overflow on deep graphs.
    static int components(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        int comps = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            comps++;
            seen[s] = true;
            stack.push(s);
            while (!stack.isEmpty()) {
                int u = stack.pop();
                // problem-specific work on u goes here
                for (int v : adj.get(u)) {
                    if (!seen[v]) { seen[v] = true; stack.push(v); }
                }
            }
        }
        return comps;
    }

    // Two-colouring check (bipartite).
    static boolean bipartite(int[][] graph) {
        int[] color = new int[graph.length];            // 0 = none, 1 / -1 = sides
        for (int s = 0; s < graph.length; s++)
            if (color[s] == 0 && !paint(graph, s, 1, color)) return false;
        return true;
    }
    private static boolean paint(int[][] graph, int u, int col, int[] color) {
        color[u] = col;
        for (int v : graph[u]) {
            if (color[v] == col) return false;
            if (color[v] == 0 && !paint(graph, v, -col, color)) return false;
        }
        return true;
    }
}

Complexity

Variations

• Component counting / sizing: launch from every unvisited node. Example: Number of Islands, Number of Provinces.
• Border-first (reverse) DFS: start from the edge and mark what is reachable. Example: Surrounded Regions, Pacific Atlantic Water Flow.
• Path enumeration with backtracking: add to path, recurse, remove. Example: All Paths From Source to Target.
• Structural copy: map originals to copies while traversing. Example: Clone Graph.
• Two-colouring: alternate colours along edges. Example: Is Graph Bipartite?
• Label then combine: paint each island with an id and size, then evaluate each flip. Example: Making A Large Island.

Common mistakes

• Bounds check after the array access instead of before it, causing ArrayIndexOutOfBoundsException.
• Launching DFS only from node 0 and missing disconnected components (bipartite and component counts need the outer loop).
• Recursion depth of 10^5+ on a long chain overflowing the Java stack; switch to an explicit Deque stack.
• Mutating the input grid when the interviewer expects it unchanged; ask, or use a separate visited array.
• In path enumeration, forgetting to remove the last node when backtracking, so paths leak into each other.

All practice problems

10 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.