Depth-First Search on Graphs

Intuition

Depth-first search walks as far as it can along one branch, then backs up to the most recent vertex that still has an unexplored edge. A visited mark guarantees every vertex is entered once, so a full traversal costs O(n + m).

Besides "which vertices can I reach", DFS hands you some structure for free:

• A DFS tree. Remembering where each vertex was discovered from gives parent pointers, and therefore a path back to the start.
• Enter / exit order. A vertex is open from the moment you enter it until all its edges are done. In a rooted tree, the vertices entered while u is open are exactly the subtree of u, which is why a subtree occupies a contiguous block of the preorder.
• Edge types. In a directed graph, an edge into a vertex that is still open (a back edge) closes a cycle. Edges into finished vertices do not.

When to use it in interviews / OAs

• Count or label groups: islands, provinces, friend circles, flood fill, "max area of island".
• Reachability: "can you open every room", "is there a path from A to B".
• Cycle detection: course prerequisites, deadlock, "is this graph a valid tree".
• Post-order work: topological order, aggregating values over subtrees.
• Exhaustive search over simple paths in small graphs or DAGs ("all paths from source to target"), which is DFS plus backtracking.
• Copying a structure: "clone graph" is DFS with a map from old vertex to new vertex.

If the question asks for the fewest steps, use BFS instead. For "connected? how many groups? any cycle?" both work and DFS is usually shorter to write.

Template

Connected components (iterative, no recursion limit)

def components(n: int, adj: list[list[int]]) -> list[int]:
    # comp[v] = id of v's component, ids are 0, 1, 2, ...
    comp = [-1] * n
    cid = 0
    for s in range(n):  # loop over every vertex: the graph may be disconnected
        if comp[s] != -1:
            continue
        comp[s] = cid
        stack = [s]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = cid  # mark on push so nothing is pushed twice
                    stack.append(v)
        cid += 1
    return comp

Flood fill on a grid

def num_islands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or seen[r][c]:
                continue
            islands += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                x, y = stack.pop()
                for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1" and not seen[nx][ny]:
                        seen[nx][ny] = True
                        stack.append((nx, ny))
    return islands

Cycle detection in a directed graph (three colors)

White = never entered, gray = open (on the current path), black = finished. Only an edge into a gray vertex proves a cycle.

import sys

WHITE, GRAY, BLACK = 0, 1, 2


def has_cycle_directed(n: int, adj: list[list[int]]) -> bool:
    sys.setrecursionlimit(max(1000, 2 * n + 10))
    color = [WHITE] * n

    def dfs(u: int) -> bool:
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:  # back edge: v is an ancestor on the current path
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

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

The recursive version is what you write on a whiteboard. For 10^5 vertices in Python, use an explicit stack of iterators; it keeps the exact enter/exit order of the recursion:

def has_cycle_directed_iter(n: int, adj: list[list[int]]) -> bool:
    color = [WHITE] * n
    for s in range(n):
        if color[s] != WHITE:
            continue
        color[s] = GRAY
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:  # resume u's edge list where we left off
                if color[v] == GRAY:
                    return True
                if color[v] == WHITE:
                    color[v] = GRAY  # "enter" v
                    stack.append((v, iter(adj[v])))
                    break
            else:  # all edges of u done: "exit" u
                color[u] = BLACK
                stack.pop()
    return False

Cycle detection in an undirected graph

Every edge appears twice in an undirected adjacency list, so the edge you arrived by must not count as a cycle. Skipping it by edge id (rather than by parent vertex) also handles parallel edges correctly.

def has_cycle_undirected(n: int, edges: list[tuple[int, int]]) -> bool:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    seen = [False] * n
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, -1)]  # (vertex, id of the edge that discovered it)
        while stack:
            u, via = stack.pop()
            for v, eid in adj[u]:
                if eid == via:
                    continue
                if seen[v]:  # a second way into v: cycle (self-loops included)
                    return True
                seen[v] = True
                stack.append((v, eid))
    return False

Complexity

O(n + m) time and O(n) extra space for the marks and the stack (or recursion). On an R x C grid that is O(R * C).

Common pitfalls

• Recursion depth. Python stops at about 1000 frames by default; a path-shaped graph with 10^5 vertices crashes a recursive DFS. Use the iterative form or raise the limit (and know the C stack can still overflow).
• Marking too late. In the stack version, mark a vertex when you push it. Marking on pop lets the same vertex sit on the stack many times.
• One visited set for directed cycles. Reaching an already finished vertex is not a cycle (think of a diamond a->b, a->c, b->d, c->d). You need the gray/black distinction.
• "Visited and not my parent" with parallel edges. Two edges between the same pair form a cycle of length 2; a parent-vertex check misses it. Compare edge ids if multi-edges are possible.
• Forgetting disconnected parts. Start a traversal from every unvisited vertex, not just vertex 0.
• Mutating the input grid to mark visits is common and fine, but say so: some interviewers want the input untouched.

Interview variations

• Boundary-first DFS. "Surrounded regions", "number of enclaves", "Pacific Atlantic water flow": start from the border cells and mark what they reach, then the answer is what was not reached.
• Valid tree. An undirected graph is a tree iff it has exactly n - 1 edges and is connected (equivalently, connected with no cycle).
• Eventual safe states. Run the three-color DFS without stopping early, and leave a vertex gray whenever a cycle is reachable from it; the vertices that end black are exactly those that cannot reach a cycle. Kahn's algorithm on the reversed graph is the alternative.
• Redundant connection. The first edge that joins two already connected vertices; union-find is the shortest code, DFS works too.
• All paths in a DAG. DFS with backtracking (append on enter, pop on exit); no visited set is needed because a DAG cannot loop.
• Clone graph / copy list with random pointer. DFS plus a hash map old -> new; create the copy on first visit so cycles terminate.