Depth-first search (DFS)

Depth-first search explores as deep as possible before backtracking, using a stack (often the call stack). O(V+E) time. Foundation of cycle detection, topological sort, strongly-connected components, and most maze/backtracking algorithms.

1. Complexity

Best	Average	Worst	Space (Worst)
`Ω(V+E)`	`Θ(V+E)`	`O(V+E)`	`O(V)`

2. How it works

From the start node, recurse into each unvisited neighbor in turn before moving to the next. With recursion the call stack tracks the path; iteratively, use an explicit stack. Pre-order vs post-order ordering matters: topological sort uses the reverse post-order.

3. Python implementation

def dfs_recursive(graph, start, visited=None):
    if visited is None: visited = set()
    visited.add(start)
    yield start
    for nbr in graph[start]:
        if nbr not in visited:
            yield from dfs_recursive(graph, nbr, visited)


def dfs_iterative(graph, start):
    """Iterative DFS using an explicit stack — avoids Python recursion limit."""
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        yield node
        # reverse so neighbors are popped in original order
        for nbr in reversed(graph[node]):
            if nbr not in visited:
                stack.append(nbr)


def topological_sort(graph):
    """Topological sort via DFS post-order. Assumes a DAG."""
    visited, order = set(), []
    def visit(n):
        if n in visited: return
        visited.add(n)
        for nbr in graph[n]:
            visit(nbr)
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]


graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(list(dfs_recursive(graph, "A")))    # ['A', 'B', 'D', 'C']
print(topological_sort(graph))            # ['A', 'B', 'C', 'D'] (or 'A', 'C', 'B', 'D')

4. Trade-offs

O(V+E) time, O(V) memory (recursion or stack depth).
Recursion can blow Python's stack on deep graphs — reach for the iterative form.
Doesn't find shortest paths; does find some path.
Foundation of: cycle detection, topological sort, Tarjan/Kosaraju SCC, articulation points, maze solving.

5. Step-by-step trace

Take the adjacency list {'A': ['B','C'], 'B': ['D','E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}. DFS starts at A and immediately descends into its first neighbour, B. From B it goes to D, which is a dead end, so it backtracks to B and tries E. From E it reaches F. F has no unvisited neighbours, so the search unwinds all the way back to A and only then explores C. By that time F is already marked visited, so C contributes no new vertex. The visit order is A, B, D, E, F, C. Breadth-first search on the same graph would instead produce A, B, C, D, E, F, finishing each level before going deeper.

The key invariant is that the recursion stack (or explicit stack) always holds the current path from the start vertex. That path is what makes DFS useful for cycle detection: an edge back to any vertex still on the stack closes a cycle.

6. Stack evolution and edge types

The iterative version replaces recursion with a list used as a stack. Each pop visits a vertex and pushes its unvisited neighbours. Because a vertex can be pushed more than once before it is visited, the loop checks visited on pop and skips duplicates; this keeps the work bounded by O(V + E).

In a directed graph, DFS classifies every edge it examines. A tree edge leads to a newly discovered vertex. A back edge leads to an ancestor still on the stack and signals a cycle. A forward edge leads to an already-finished descendant, and a cross edge leads to a finished vertex in another branch. Tracking three colours (white = unseen, grey = on stack, black = finished) is enough to tell them apart.

7. Worked example: cycle detection in a directed graph

WHITE, GREY, BLACK = 0, 1, 2

def has_cycle(graph):
    color = {v: WHITE for v in graph}
    def visit(u):
        color[u] = GREY
        for v in graph[u]:
            if color[v] == GREY:          # back edge
                return True
            if color[v] == WHITE and visit(v):
                return True
        color[u] = BLACK
        return False
    return any(color[v] == WHITE and visit(v) for v in graph)

print(has_cycle({'a': ['b'], 'b': ['c'], 'c': ['a']}))   # True
print(has_cycle({'a': ['b'], 'b': ['c'], 'c': []}))      # False

The same three-colour walk underlies topological sorting (emit vertices in reverse finishing order), Tarjan's strongly connected components, and finding bridges and articulation points in undirected graphs.

8. When to use DFS versus alternatives

Goal	Use	Why
Reachability, connected components	DFS or BFS	Both O(V+E); DFS is shorter to write recursively
Cycle detection, topological order, SCCs	DFS	Relies on the stack path and finishing times
Shortest path, unweighted	BFS	DFS finds a path, not the shortest one
Shortest path, weighted	Dijkstra	Needs a priority queue over distances
Puzzles, permutations, constraint search	DFS with backtracking	Memory proportional to depth, not breadth

9. Pitfalls

Recursion depth. CPython's default limit is about 1000 frames, so recursive DFS on a long path graph raises RecursionError. Use the iterative form for large inputs.
Marking too late. In the iterative form, marking on pop (as above) is correct for visit order; marking on push changes the order and is a frequent source of off-by-one differences from expected output.
Disconnected graphs. A single call only covers one component; loop over all vertices for full coverage.
Undirected cycles. In undirected graphs every edge appears twice, so ignore the edge back to the immediate parent when checking for cycles.

Finally, remember that visit order depends on adjacency order. Two correct DFS implementations can print different sequences for the same graph if one iterates neighbours in insertion order and the other in sorted or reversed order. When a test expects a specific order, match the neighbour iteration exactly rather than assuming the traversal is wrong.

← Back to Algorithms