Graph Algorithms · 02 / 11

DFSDepth-first search

Go as deep as possible then back out; the basis of components and topological sort.

Used for: Walking folders, flood fill, detecting circular dependencies

Time complexityO(V+E)

Space complexityO(V)

DifficultyIntro

PrerequisitesStacks, recursion, adjacency lists

01Why it exists

Working out how large a folder is

Finder, or the du command, has to work out how much space a folder takes up: step into a subfolder, total it up, come back to the parent and add it in, and keep going down until there are no subfolders left.

Why this fitsGo in, finish the work, come back out — that is exactly the recursive structure of DFS. Anything tree-shaped (a file system, the DOM, a JSON document) is almost always walked with DFS.

The paint bucket in an image editor

One click and the entire connected patch of the same colour is filled in. Flood fill in image processing, clearing connected same-coloured tiles in a game, counting islands on a map — all of them are about finding a connected region.

Why this fitsDFS starts at one cell and covers everything it can reach; what it covers is one connected component. The code is shorter than BFS, just a few lines with recursion.

Detecting circular dependencies

Module A imports B, B imports C, and C imports A again; a bundler has to catch that cycle before it causes trouble. Spreadsheet formulas that reference each other and package version constraints behave the same way.

Why this fitsDFS can tell a node that is still being explored apart from one that is finished. Reaching a node that is still being explored means there is a cycle. BFS cannot make that distinction.

Reach for it when you see:Connected regions, flood fill, whether a cycle exists, all paths or all combinations, walking a tree structure, needing to backtrack.

02The core idea

DFS picks one path and keeps going deeper until there is no road left, then backs up to the last fork, where it takes another route it has not tried. That order — deep first, back up afterwards — is exactly the last-in-first-out behaviour of a stack, which is why recursion is the most natural way to write it: the call stack already is the stack you need.

Compared with BFS, DFS makes no promise about the shortest path, but it does remember how it got to where it is, and that path information is what makes it the foundation for cycle detection, connected components, topological sorting and enumerating every path.

Every node passes through three states: undiscovered, in progress (entered, but its neighbours are not all done, so it is still sitting on the stack) and finished (every neighbour handled, popped off the stack). A great deal of the advanced work rests on that distinction — running into a node that is still in progress, for example, means the graph contains a cycle.

03The algorithm

1Call dfs(u) on the start node, mark u as discovered, and record it in the visit order.
2Look at each neighbour v of u in turn: if v has not been discovered, recurse into dfs(v) immediately, finishing the path through v before coming back for the next neighbour.
3Once every neighbour of u has been seen, dfs(u) returns — it backtracks to the node that called it.
4When the start node's dfs returns, every node reachable from the start has been visited. To cover the whole graph, call it again on each node that is still undiscovered; each of those calls is one connected component.

04Interactive demo

The same graph, again starting at A, with neighbours taken in alphabetical order. Watch the stack grow tall and shrink back, and look at the visit numbers under the nodes: nothing like the level order BFS produced.

UndiscoveredOn the stackProcessingDone

Call stack (bottom → top)

empty

Visit order

Not started yet

Step 0/17Call dfs(A) on the start node.

05Code

The recursive version sits closest to the idea. On a deep graph it can exceed the recursion limit, and that is when you switch to an explicit stack, the iterative version.

def dfs(adj, start):
    # adj: dict[node, list[node]]. Returns the visit order.
    order = []
    visited = set()

    def go(u):
        visited.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in visited:
                go(v)                # finish the path through v before the next neighbour
        # this is u's "finished" moment (the backtracking point)

    go(start)
    return order


def dfs_iterative(adj, start):
    # An explicit stack instead of recursion; the order may differ slightly from the recursive version
    order, visited = [], set()
    stack = [start]
    while stack:
        u = stack.pop()              # take from the top
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        for v in reversed(adj[u]):    # push in reverse so the first neighbour comes off first
            if v not in visited:
                stack.append(v)
    return order

06Practice

LeetCode 695Max Area of IslandMedium
LeetCode 133Clone GraphMedium
LeetCode 797All Paths From Source to TargetMedium
LeetCode 207Course ScheduleMedium
LeetCode 547Number of ProvincesMedium

PreviousBFS NextGrid as Graph