Depth-first search (DFS) explained: how it works, code and complexity

What problem DFS solves

DFS answers the question "what can I reach from here?" by exploring one branch completely before trying the next. That order is useful whenever the structure of paths matters more than their length: finding a way out of a maze, checking whether a graph has a cycle, ordering tasks that depend on each other, or listing all solutions of a puzzle.

Unlike breadth-first search, DFS does not find shortest paths. Its strength is that it keeps only the current path in memory and that it naturally records when a node is entered and when it is finished.

The idea in plain words

1. Mark the current node as visited.
2. For each neighbor that is not visited, move to it and repeat step 1 from there.
3. When a node has no unvisited neighbors left, it is finished: go back to the node you came from.
4. When you return to the start node and it has no unvisited neighbors, the search is complete.

Going back to the previous node is called backtracking. With recursion, the call stack does this for you.

Worked example, step by step

Use the same undirected graph as in the BFS article: A–B, A–C, B–D, C–D, C–E, D–F. Start at A and try neighbors in alphabetical order.

The visiting order is A, B, D, C, E, F. The finishing order is E, C, F, D, B, A. Finishing order is what topological sort and strongly connected component algorithms use.

Python implementation

The recursive version is the shortest and closest to the idea:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

A list keeps the example readable but makes in an O(n) check. For large graphs, keep a separate set for membership. The iterative version uses an explicit stack and avoids Python's recursion limit. Neighbors are pushed in reverse so they are popped in the original order:

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

Note the difference from BFS: here a node is marked when it is popped, so it may sit on the stack more than once. That is correct for DFS and keeps the true depth-first order.

Detecting a cycle in a directed graph

A classic DFS application colors each node: white (not seen), gray (on the current path) and black (finished). Reaching a gray node means there is an edge back into the current path, which is a cycle.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

Time and space complexity

Variants and common mistakes

• Pre-order and post-order: record a node when you enter it (pre-order) or when you finish it (post-order). Reverse post-order of a directed acyclic graph is a topological order.
• Connected components: start a new DFS from every node that is still unvisited; each start is one component.
• Iterative deepening DFS: run DFS with a depth limit 0, 1, 2, … It finds shortest paths like BFS with the low memory of DFS.
• Flood fill on a grid (the paint bucket tool) is DFS or BFS over neighboring cells of the same color.

Other frequent bugs: forgetting the visited set (infinite loop on any cycle), using a mutable default argument such as visited=[] (it is shared between calls), and treating an undirected edge back to the parent as a cycle.

When to use DFS and real-world uses

• Use DFS for reachability, cycle detection, topological sort, connected and strongly connected components, bridges and articulation points, and for exhaustive search with backtracking.
• Use BFS instead when you need the fewest steps, and Dijkstra or A* when edges have weights.
• Interview problems: number of islands, clone a graph, course schedule (cycle detection), path sum in a binary tree, generating permutations.
• Real world: build systems and package managers resolving dependency order, compilers analysing control flow, maze generation, and tree walks over file systems or HTML documents.