Depth First Search — Tech Epitome

Depth First Search

Follow one path to exhaustion, then retreat and try the next.

Medium8 problems

How do I recognise this pattern?

Counting connected components, islands, or regions.
Detecting a cycle in a graph.
Tree traversals and whole-subtree properties.
Topological ordering of dependencies.
Any question about a complete path from root to leaf.

When it is the wrong tool

You need the shortest path on an unweighted graph — DFS finds *a* path, not the shortest.
The graph is very deep and the language has a modest recursion limit; convert to an explicit stack.
The answer depends on processing nodes in distance order.

What is it?

Go as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is the natural fit for questions about connectivity, structure, and whole-path properties — anything where you must fully explore a region before drawing a conclusion about it.

The core idea

Decide whether your work happens on the way down (pre-order) or on the way back up (post-order). Subtree aggregates and topological order require post-order; that choice is most of the algorithm.

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

Python

1def count_components(graph):2    visited = set()3    components = 04 5    def explore(node):6        visited.add(node)7        for nxt in graph[node]:8            if nxt not in visited:9                explore(nxt)10 11    for node in graph:12        if node not in visited:13            components += 114            explore(node)15 16    return components17 18 19def has_cycle_directed(graph):20    """Three colours: unvisited, in the current path, fully done."""21    UNVISITED, IN_PATH, DONE = 0, 1, 222    state = {node: UNVISITED for node in graph}23 24    def explore(node):25        state[node] = IN_PATH26        for nxt in graph[node]:27            # A back-edge to something still on the stack is a cycle.28            # An edge to a DONE node is merely a re-convergence.29            if state[nxt] == IN_PATH:30                return True31            if state[nxt] == UNVISITED and explore(nxt):32                return True33        state[node] = DONE34        return False35 36    return any(explore(n) for n in graph if state[n] == UNVISITED)

Common mistakes

Using a two-state visited set for cycle detection in a directed graph, which reports a cycle for any re-convergent path.
Recursing without a visited check, looping forever on a cyclic graph.
Doing aggregate work pre-order when the children's results are needed.
Hitting the recursion limit on a long path and mistaking the stack overflow for a logic bug.

Problems using Depth First Search

Problem	Difficulty	Role
Paint Bucket Region#91	Easy	Related
Unlock Every Vault#93	Easy	Primary
Coastline Length#94	Easy	Primary