DFS — Going Deep First

What is it? #

Depth-first search picks one path and follows it as far as possible, then backs up and tries the next option.

It uses a stack — either an explicit one, or the call stack through recursion. Recursion is usually shorter to write; an explicit stack avoids hitting the recursion limit on deep graphs.

DFS does not find shortest paths. It finds a path, and it explores the whole reachable region eventually. What it is good at is questions about structure: is there a cycle, what are the connected components, in what order can these tasks run.

It also underpins backtracking: try a choice, recurse, and undo the choice if it leads nowhere.

Think of it like this #

Exploring a cave system by always taking the leftmost tunnel and unrolling string behind you. When you reach a dead end, you follow the string back to the last junction and take the next tunnel.

BFS would be more like sending a hundred people to check every tunnel one step at a time. DFS is one person, going deep.

Simple example #

You have a build system where tasks depend on other tasks. You need a valid order to run them, and you need to detect circular dependencies. Both fall out of DFS.

Code #

graph = {
    "a": ["b", "c"],
    "b": ["d"],
    "c": ["d", "e"],
    "d": ["f"],
    "e": ["f"],
    "f": [],
}


# Recursive DFS — short and clear
def dfs_recursive(graph, node, seen=None, order=None):
    seen = set() if seen is None else seen
    order = [] if order is None else order
    if node in seen:
        return order
    seen.add(node)
    order.append(node)
    for neighbour in graph[node]:
        dfs_recursive(graph, neighbour, seen, order)
    return order

print(dfs_recursive(graph, "a"))     # ['a', 'b', 'd', 'f', 'c', 'e']


# Iterative DFS — no recursion limit to worry about
def dfs_iterative(graph, start):
    seen, stack, order = set(), [start], []
    while stack:
        node = stack.pop()               # pop from the end = depth first
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):
            if neighbour not in seen:
                stack.append(neighbour)
    return order

print(dfs_iterative(graph, "a"))


# Topological sort: a valid task order, built from DFS finish times
def topological_order(graph):
    seen, visiting, order = set(), set(), []

    def visit(node):
        if node in seen:
            return
        if node in visiting:
            raise ValueError(f"Cycle detected at {node}")
        visiting.add(node)
        for neighbour in graph[node]:
            visit(neighbour)
        visiting.discard(node)
        seen.add(node)
        order.append(node)               # added after all dependencies

    for node in graph:
        visit(node)
    return order[::-1]                   # reverse for dependency order

print(topological_order(graph))          # ['a', 'c', 'e', 'b', 'd', 'f']


# Backtracking: try a choice, undo it if it fails
def find_path(graph, node, goal, path=None, seen=None):
    path = [] if path is None else path
    seen = set() if seen is None else seen
    path.append(node)
    seen.add(node)
    if node == goal:
        return list(path)
    for neighbour in graph[node]:
        if neighbour not in seen:
            found = find_path(graph, neighbour, goal, path, seen)
            if found:
                return found
    path.pop()                           # undo — this branch did not work
    return None

print(find_path(graph, "a", "e"))        # ['a', 'c', 'e']

BFS vs DFS

                 BFS                     DFS
structure        queue                   stack or recursion
explores         level by level          one path to the end
shortest path    yes (unweighted)        no
memory           whole level             current path depth
good for         nearest, hops           cycles, ordering, backtracking

How it works #

The recursive version marks a node seen, records it, then immediately recurses into the first neighbour. Only when that entire branch is exhausted does it move to the second neighbour — that is what "depth first" means.

The iterative version uses an explicit list as a stack. pop() takes from the end, so the most recently added neighbour is explored next. Pushing neighbours in reverse makes the visit order match the recursive version.

Checking if node in seen: continue after popping is necessary in the iterative form, because a node can be pushed more than once before it is processed.

topological_order appends a node only after all of its dependencies have been visited. Reversing the result gives an order where every task appears before the tasks that depend on it. The visiting set catches cycles: reaching a node that is still in progress means the dependencies loop.

find_path shows backtracking. It appends the node to the path, explores, and if nothing works it pops the node off before returning. That undo step is the essence of backtracking, and the same pattern solves sudoku, n-queens and permutation problems.

Both versions are O(V + E). Memory differs: DFS holds only the current path, so it is often lighter than BFS on wide graphs — but deeper, which is why recursion can overflow.

Real-world use #

Build tools and package managers use topological sorting to decide execution order and to report circular dependencies. Spreadsheet engines do the same for formula recalculation.

Compilers walk syntax trees with DFS. Static analysis tools traverse call graphs the same way.

File system operations — calculating folder sizes, finding all files matching a pattern, deleting a tree — are DFS, usually post-order.

Backtracking solves constraint problems: scheduling, resource allocation, puzzle solvers, regular expression matching. The idea of "try, recurse, undo" is what makes exhaustive search manageable.

Cycle detection appears in less obvious places too: detecting circular imports, circular foreign key references, and loops in permission inheritance.

Common mistakes #

• Omitting the visited set, causing infinite recursion on a cycle.
• Using recursion on a very deep graph and hitting RecursionError — switch to the iterative form.
• Expecting DFS to return the shortest path. It returns whatever path it finds first.
• Forgetting to undo state when backtracking, so later branches see stale data.
• Confusing the two DFS sets in cycle detection: one for "in progress", one for "finished".

Practice #

Write a DFS that returns all connected components of an undirected graph. Then write a topological sort for a set of build tasks and make it raise a clear error naming the nodes involved when a cycle exists.