Depth-first search

What this chapter covers

Depth-first search is the other foundational graph traversal, and it's BFS's mirror image in the most literal way: take last chapter's breadth-first code and swap the queue for a stack, and "nearest first" becomes "deepest first." Instead of expanding outward in rings, DFS commits to one branch and follows it as far as it goes, backing up only when it dead-ends. That change costs it the shortest-path guarantee — but it buys a different set of powers that BFS can't match cheaply. Because DFS's recursion mirrors the structure of the graph, the order in which nodes finish gives topological orderings, an edge back to an ancestor still on the stack detects a cycle, and one DFS per component enumerates them. This chapter builds it both ways — recursively and with an explicit stack — watches it plunge down a branch, and races it against BFS on the one axis where DFS wins decisively: memory.

A bit of history

Depth-first search is old enough to predate computers entirely. In the 1880s the French mathematician Charles Pierre Trémaux described a procedure for threading a maze — follow a passage, marking it, until you hit a dead end or a junction you've seen, then back up to the last untried branch — which is exactly DFS with the marks standing in for the visited set. It stayed a maze-solving curiosity until the 1970s, when John Hopcroft and Robert Tarjan turned it into the engine of modern graph theory. Their insight was that DFS doesn't just visit a graph; the tree it builds, and the timestamps of when each node is entered and finished, expose deep structure. In a burst of papers around 1972–1973 they used DFS to test planarity, find biconnected and strongly connected components, and more — all in linear time, where the previous algorithms were quadratic or worse. Tarjan's strongly-connected-components algorithm, still standard today and covered later in this tier, is pure DFS bookkeeping. That's the through-line: BFS is the shortest-path traversal, but DFS is the structure-revealing one.

The intuition

Start at a node, mark it seen, and recurse into its first unseen neighbor. Then recurse into that node's first unseen neighbor, and keep going deeper — you don't touch the start's second neighbor until the entire subgraph reachable through the first one has been fully explored and you've backtracked all the way out. When a node has no unseen neighbors left, you return from it (pop it off the stack) and resume wherever you were. The traversal traces a single long tendril into the graph, retracts, threads a different tendril, and so on until everything reachable is covered.

The mechanism is a stack, and usually it's the call stack — DFS is the traversal recursion writes for free, because a recursive call is a push and a return is a pop. That's the entire difference from BFS: BFS's queue serves the oldest-discovered node next (breadth), DFS's stack serves the newest-discovered node next (depth). Same visited set, same O(V+E) cost, same "touch every vertex and edge once" — one data-structure swap flips the whole character of the search. And it's why DFS's memory is so different: at any instant the stack holds only the nodes on the current path from the root, so its working set is the depth of the search, not the width.

Complexity: how it scales

DFS is $O(V + E)$ time, exactly like BFS: each vertex is visited once and each edge examined once. The recurrence for the recursive form is $T(V,E) = \Theta(V + E)$ — there's no branching blowup because the visited set stops re-exploration. Where the two traversals genuinely diverge is peak memory. BFS's queue swells to the size of the widest level of the graph; DFS's stack only ever holds the current path, so its peak is the graph's depth. On a graph that is wide and shallow, that gap is enormous, and that's what the face-off measures — peak working memory on complete binary trees as they grow:

On a complete binary tree of height 12 — 8191 nodes — DFS's recursion never held more than 13 nodes at once (the root-to-leaf depth), while BFS's queue peaked at 4096 (the entire bottom level). That's 315 times less memory for DFS, on the identical graph, and the gap widens with every level added because the bottom level doubles while the depth grows by one. This is the honest mirror of last chapter's result: BFS won on path quality by a factor of ten, and here DFS wins on memory by a factor of hundreds. Neither traversal dominates; they trade the queue's breadth for the stack's depth.

What it's good at, what it isn't

DFS is the right tool whenever the structure of the graph is the question rather than the distance. Its finish-order (the sequence in which nodes are fully explored) reversed is a topological sort of a DAG — next chapter. A back edge to a node still on the recursion stack is a cycle, which is how you detect deadlocks, circular dependencies, and infinite loops in build graphs. Running one DFS per unvisited node partitions a graph into connected components; a more careful version (Tarjan's) finds strongly connected components in a directed graph. DFS also underlies backtracking search — N-Queens, Sudoku, constraint solving — because "try a choice, recurse, undo on failure" is DFS over the tree of partial solutions. And on wide graphs its memory frugality is decisive.

Where DFS is the wrong tool is anything about shortest paths or nearest-first order. The path DFS finds between two nodes is a path, often a wildly indirect one — last chapter's face-off had it running ten times longer than BFS's shortest path. If you want fewest steps, use BFS; if you want fewest weighted cost, use Dijkstra. DFS also has the recursion-depth hazard on deep graphs described in the deep dive, and unlike BFS it gives no distance information for free.

The data, or the inputs

The face-off runs on complete binary trees of growing height, the cleanest graph shape for exposing the depth-versus-width memory split: their depth grows by one per level while their widest level doubles. The correctness check runs DFS (both forms) and BFS on random graphs to confirm they reach the same set of nodes, and checks the three-color cycle detector against an independent Kahn-style peel on random DAGs with and without a planted cycle. The animation runs the recursive DFS on the same 2×4 grid graph BFS explored last chapter, so you can lay the two traversals side by side.

Build it, one function at a time

The recursive traversal — the call stack is the stack:

def dfs_recursive(adj, start, order=None, seen=None):
    """Explore depth-first from `start` using the CALL STACK as the stack. Visit a node,
    then recurse into its first unseen neighbor, going as deep as possible before
    backtracking. O(V + E): each vertex is visited once, each edge examined once. The
    recursion depth is the length of the current root-to-here path — DFS's whole memory
    footprint. Returns the visit order."""
    if order is None:
        order, seen = [], set()
    seen.add(start)
    order.append(start)
    for v in adj[start]:
        if v not in seen:
            dfs_recursive(adj, v, order, seen)   # go deep before going wide
    return order

The same traversal made explicit, so it can't overflow on deep graphs:

def dfs_iterative(adj, start):
    """The same traversal with an EXPLICIT stack instead of recursion — the honest
    picture of what the call stack was doing, and the version that won't overflow on a
    graph deeper than Python's recursion limit. Push the start; repeatedly pop a node,
    and if it's unseen, visit it and push its neighbors. We mark on POP (not on push), so
    a node can sit on the stack more than once — that's the price of the explicit form."""
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(adj[u]):      # reversed → visit neighbors in the same order as the recursive version
            if v not in seen:
                stack.append(v)
    return order

And DFS's signature capability — detecting a cycle with three colors:

def has_cycle_directed(adj):
    """DFS's signature trick: detect a cycle in a directed graph in O(V+E) using three
    colors. WHITE = untouched, GRAY = on the current recursion stack (being explored),
    BLACK = fully finished. An edge to a GRAY node is a BACK EDGE — it points to an
    ancestor still open on the stack, which means we've found a cycle. This is exactly
    what BFS cannot see cheaply, and it's the basis of topological sort next chapter."""
    n = len(adj)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def visit(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge to an ancestor on the stack → cycle
                return True
            if color[v] == WHITE and visit(v):
                return True
        color[u] = BLACK
        return False

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

Watch it work

Here's the recursive DFS on the same 2×4 grid from the BFS chapter, starting at node 0. Orange is the node being visited right now; blue nodes are the recursion stack — the active path from the root down to the current node; green nodes are done (visited and backtracked past); dark nodes are undiscovered. Watch it plunge: from 0 it goes to 1, then 2, then 3, then drops to 7 and threads back along the bottom row — a single long tendril, not a wave. Compare it directly with last chapter's BFS, which lit up the whole ring at each distance. Same graph, same start; the queue fanned out, the stack bores in:

The complete code

Both versions in one place — flip between them. The from-scratch tab is DFS three ways (recursive, iterative, and the three-color cycle detector) plus the peak-memory probes. The library tab is the reference DFS/BFS the traces are checked against, with the networkx calls you'd actually use in production noted at the top.

"""Depth-first search — the other foundational graph traversal, and BFS's mirror
image. Swap BFS's queue for a stack and "nearest first" becomes "deepest first":
DFS plunges down one branch as far as it can go, and only when it dead-ends does it
back up and try the next branch.

That single change — stack instead of queue — costs DFS the shortest-path guarantee
(the path it finds can wander), but buys a different set of powers. DFS's recursion
naturally exposes structure BFS can't see as cheaply: the order nodes FINISH (all
descendants done) gives topological orderings, a back edge to an ancestor still on
the stack detects a cycle, and one DFS per unvisited node enumerates connected
components. And on a graph that is wider than it is deep, DFS's memory is a single
root-to-leaf path where BFS must hold an entire level.
"""
from collections import deque


# region: dfs_recursive
def dfs_recursive(adj, start, order=None, seen=None):
    """Explore depth-first from `start` using the CALL STACK as the stack. Visit a node,
    then recurse into its first unseen neighbor, going as deep as possible before
    backtracking. O(V + E): each vertex is visited once, each edge examined once. The
    recursion depth is the length of the current root-to-here path — DFS's whole memory
    footprint. Returns the visit order."""
    if order is None:
        order, seen = [], set()
    seen.add(start)
    order.append(start)
    for v in adj[start]:
        if v not in seen:
            dfs_recursive(adj, v, order, seen)   # go deep before going wide
    return order
# endregion


# region: dfs_iterative
def dfs_iterative(adj, start):
    """The same traversal with an EXPLICIT stack instead of recursion — the honest
    picture of what the call stack was doing, and the version that won't overflow on a
    graph deeper than Python's recursion limit. Push the start; repeatedly pop a node,
    and if it's unseen, visit it and push its neighbors. We mark on POP (not on push), so
    a node can sit on the stack more than once — that's the price of the explicit form."""
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(adj[u]):      # reversed → visit neighbors in the same order as the recursive version
            if v not in seen:
                stack.append(v)
    return order
# endregion


# region: has_cycle
def has_cycle_directed(adj):
    """DFS's signature trick: detect a cycle in a directed graph in O(V+E) using three
    colors. WHITE = untouched, GRAY = on the current recursion stack (being explored),
    BLACK = fully finished. An edge to a GRAY node is a BACK EDGE — it points to an
    ancestor still open on the stack, which means we've found a cycle. This is exactly
    what BFS cannot see cheaply, and it's the basis of topological sort next chapter."""
    n = len(adj)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def visit(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge to an ancestor on the stack → cycle
                return True
            if color[v] == WHITE and visit(v):
                return True
        color[u] = BLACK
        return False

    return any(color[u] == WHITE and visit(u) for u in range(n))
# endregion


# region: peak_memory
def peak_dfs_depth(adj, start):
    """Peak DFS memory = the deepest the recursion ever got = the longest root-to-here
    path DFS walked. On a graph wider than it is deep, this is tiny."""
    seen = set()
    peak = 0
    stack = [(start, 1)]
    while stack:
        u, depth = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        peak = max(peak, depth)
        for v in adj[u]:
            if v not in seen:
                stack.append((v, depth + 1))
    return peak


def peak_bfs_frontier(adj, start):
    """Peak BFS memory = the widest the queue ever got = the largest level (ring of one
    distance). On a wide, shallow graph this is the whole bottom level — huge."""
    seen = {start}
    peak = 0
    q = deque([start])
    while q:
        peak = max(peak, len(q))
        u = q.popleft()
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                q.append(v)
    return peak
# endregion

"""The library counterpart. In real work you don't hand-roll graph traversal — you
reach for networkx, which gives you dfs_preorder_nodes, dfs_tree, find_cycle,
topological_sort, and connected_components, all built on the DFS in impl.py.

    import networkx as nx
    G = nx.DiGraph(); G.add_edges_from(edges)
    list(nx.dfs_preorder_nodes(G, source))   # the visit order
    nx.find_cycle(G)                          # raises if acyclic, else returns the cycle
    list(nx.topological_sort(G))              # DFS finish-order, reversed

networkx is the real, batteries-included graph library, but its traversals are the
exact algorithm in impl.py — a stack, a visited set, O(V+E). To keep this chapter's
data reproducible with the standard library alone, the trace generator checks our DFS
against the plain references below (and the BFS it's raced against for memory).
"""
from collections import deque


# region: reference
def dfs_reference(adj, start):
    """A minimal recursive DFS, the ground truth for the visit order."""
    seen, order = set(), []

    def go(u):
        seen.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                go(v)

    go(start)
    return order


def bfs_order(adj, start):
    """Plain BFS — the queue-based sibling DFS is compared against."""
    seen = {start}
    order = []
    q = deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                q.append(v)
    return order


def has_cycle_reference(adj):
    """Kahn-style acyclicity check (peel off in-degree-0 nodes) — an independent way to
    confirm the DFS three-color cycle detector, using no recursion at all."""
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    removed = 0
    while q:
        u = q.popleft()
        removed += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return removed != n     # couldn't remove everyone → a cycle held some nodes back
# endregion

Scratch vs library

DFS and BFS have identical complexity, so the comparison — as with last chapter — isn't about speed, it's about which property you need. BFS gave you shortest paths; DFS gives you structure and small memory. The face-off made the memory difference concrete: 315× less on a wide tree. But the deeper lesson is that these two traversals are a matched pair, distinguished by one data-structure choice, and almost every graph algorithm in this tier is one of them with extra bookkeeping bolted on. Topological sort is DFS plus finish-times. Dijkstra is BFS plus a priority queue. Tarjan's components are DFS plus low-link numbers. Learning to see a new graph algorithm as "BFS or DFS, plus what?" is most of what it takes to read this tier fluently. When you reach for a graph library like networkx, its dfs_preorder_nodes, find_cycle, and topological_sort are all this same stack-based walk — the library saves you the bookkeeping, not the understanding.

Where you'll actually meet it

DFS is everywhere structure matters. Build systems (make, bazel, npm, cargo) run it over the dependency graph to order compilation and to reject circular dependencies. Spreadsheet engines use it to recompute cells in dependency order and to flag circular references. Garbage collectors mark reachable objects with it. Compilers use it for control-flow and data-flow analysis. Every backtracking solver — Sudoku, N-Queens, regex engines, constraint solvers, maze generators — is DFS over a tree of choices. File-system walkers (os.walk, find) are DFS over directories. And the heavy graph algorithms — strongly connected components, biconnectivity, articulation points, topological sort — are all Hopcroft and Tarjan's DFS with timestamps. Wherever the question is "what depends on what," "is there a cycle," or "explore this space cheaply," DFS is the tool.

Takeaways

Depth-first search explores a graph by committing to one branch and following it to the end before backtracking, driven by a stack — usually the call stack, which is why recursion writes it for free. It's BFS with the queue swapped for a stack, and that one change trades breadth and shortest paths for depth, structure, and O(depth) memory: on a wide tree it used 315× less memory than BFS. It doesn't find shortest paths, and its recursive form can overflow the stack on deep graphs — reach for the explicit-stack version then.

DFS's real value shows up next chapter, where the order in which it finishes nodes turns out to be a topological ordering of a directed acyclic graph — the correct sequence to run tasks whose dependencies form a graph. Topological sort is the first of several classic algorithms that are, at their core, a depth-first search keeping one extra piece of bookkeeping.