Hand a graph to recursion and what falls out is depth-first search: commit to one path as far as it goes, then back up to the last junction with something unexplored and dive again. The elegant part is what's missing. There are no breadcrumbs and no parent pointers, because the call stack already holds the exact chain of junctions between the start and wherever the search currently stands.

DFS visits every node and edge reachable from the start in O(V + E) time, and it's the engine under flood fill, island counting, cycle detection, and backtracking itself. The one thing it never promises is a shortest path, and the one thing it always demands is a visited set.

Take a small undirected graph as an adjacency list, neighbors in ascending order: 0: [1, 2], 1: [0, 3, 4], 2: [0, 4], 3: [1, 5], 4: [1, 2, 5], 5: [3, 4]. Starting at 0, the walk enters 1 (its first unvisited neighbor), then 3, then 5. Now predict the next node before reading on: 5's neighbors are 3 and 4.

It's 4, since 3 is already marked, and from 4 the walk reaches 2, finishing the order 0, 1, 3, 5, 4, 2. Notice the path went five nodes deep before node 2, a direct neighbor of the start, ever got visited. That's the personality of the algorithm. Two details carry the correctness: the visited set (this graph has cycles, and without marks the walk loops between 3 and 5 forever), and the fact that the visit order depends entirely on how neighbors are listed. Reorder an adjacency list and a different valid DFS comes out.

def dfs(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = set()
    order = []

    def explore(node: int) -> None:
        # Mark on entry, before touching any neighbors
        visited.add(node)
        order.append(node)

        for neighbor in graph[node]:
            # Skip anything already claimed, or cycles loop forever
            if neighbor not in visited:
                explore(neighbor)

    explore(start)
    return order

Recursion is borrowed memory, and the loan has a limit. Python caps the call stack around 1,000 frames by default, and a path-shaped graph of 100,000 nodes will blow through any raised limit into a hard crash. The fix is mechanical: own the stack yourself. Push the start, then loop: pop a node, visit it, push its unvisited neighbors.

def dfs_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = {start}
    order = []
    stack = [start]

    while stack:
        node = stack.pop()
        order.append(node)

        # Push in reverse so the first-listed neighbor pops first
        for neighbor in reversed(graph[node]):
            # Mark on push: one stack entry per node, no duplicates
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    return order

Two choices in that code earn their comments. Neighbors are pushed in reverse so the first-listed neighbor sits on top and pops first, which makes this version reproduce the recursive order exactly. And nodes are marked when pushed, not when popped: mark on pop and the same node can be sitting in the stack several times, pushed by several different neighbors, quietly multiplying the work.

You might think the first path DFS finds to a target is the shortest one. It almost never is. In the walk above, DFS reached node 4 by the route 0 → 1 → 3 → 5 → 4, four edges, when 0 → 1 → 4 exists at two. DFS commits to corridors, and a committed walker takes whatever scenic route the adjacency order dictates. When the question contains the words "shortest" or "minimum steps" on an unweighted graph, the tool is breadth-first search, which explores in rings and reaches everything by a minimum-edge path first.

The other boundary worth drawing is with backtracking. Same recursive skeleton, opposite relationship with the visited marks: DFS marks a node once and never unmarks, because it wants to traverse everything exactly once. Backtracking marks, recurses, and unmarks, because it wants every path, not every node. Word Search sits right on the boundary: a DFS over the grid that must unmark cells on the way out so other paths can reuse them.

The flood-fill family dominates: Number of Islands launches a DFS from each unvisited land cell and sinks the whole island, so the number of launches is the number of islands, and Max Area of Island is the same walk returning the count of cells it flooded. Surrounded Regions inverts the target: flood from the border first, and whatever the flood never touched is what gets captured. Pacific Atlantic flips direction entirely, climbing inward from each ocean's edge and intersecting the two reachable sets.

Beyond grids, cycle detection runs DFS with three node states (unvisited, on the current path, finished), where finding an on-path node means a directed cycle, which is how Course Schedule decides whether the prerequisites are satisfiable. And connected-component counting is the simplest pattern of all: loop over every node, launch DFS on the unvisited ones, count the launches.

DFS code is short, and these are the five places it goes wrong anyway:

Two checks before diving into the set: why must a node be marked before its neighbors are explored rather than after, and what does the number of DFS launches over a grid count? The problems run flood fill first, then the direction-flipping tricks, then cycle detection: