Depth-First Search

Follow one path as far as it goes, then backtrack. The basis for cycle detection, topological sort, and exhaustive search.

Level: intermediate

What is it?

Depth-first search (DFS) explores a graph by going as deep as possible along each branch before backtracking. It is naturally recursive (the call stack remembers the way back) or can use an explicit stack. A visited set prevents infinite loops on cycles. Recording the order in which vertices finish yields a topological ordering of a DAG.

Why does it matter?

DFS answers structural questions — is there a cycle, which vertices are connected, what is a valid build order, can this maze be solved — in linear time. It is also the engine of backtracking search over puzzles and combinations.

Mental model

Exploring a cave with a ball of string. Go down a tunnel as far as it goes, and at a dead end wind the string back to the last fork and try the next tunnel. The string is the stack of choices you can still return to.

How it works

Recursive form: mark visited, recurse into each unvisited neighbor.
Iterative form: an explicit stack avoids recursion limits on deep graphs.
Time O(V + E); space O(V) for the visited set plus O(depth) for the stack.
Detect a cycle in a directed graph by finding an edge to a vertex still on the current path.
Topological sort: order vertices by decreasing finish time (or use Kahn's algorithm).
Backtracking is DFS over the tree of choices, with a step that undoes each choice.

Steps

Mark the vertex visited
Pick an unvisited neighbor
Recurse deeper
At a dead end, return
Try the next neighbor

Code example: Recursive depth-first traversal

def dfs(graph, node, seen=None):
    seen = set() if seen is None else seen
    seen.add(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(graph, nxt, seen)
    return seen

g = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []}
print(sorted(dfs(g, "A")))   # ['A', 'B', 'C', 'D']

Complexity and trade-offs

Time: O(V + E)

Space: O(V) for the visited set; O(depth) for the stack

Trade-offs

Low memory on wide graphs and a natural fit for recursion
Does not find shortest paths
Deep recursion can overflow the stack

Real-world usage

Cycle detection and topological sorting of dependencies
Connected components and maze solving
Backtracking: Sudoku, N-Queens, and permutations

Common mistakes

Forgetting a visited set and looping forever on a cycle.
Using DFS for shortest paths.
Recursing on a huge path graph and hitting the recursion limit.

Interview questions

How do you detect a cycle in a directed graph with DFS?

Track vertices currently on the recursion path. If you reach a neighbor that is on that path, there is a back edge, and therefore a cycle. Vertices finished earlier do not count.

How does DFS give a topological order?

Run DFS and append each vertex to a list after all its descendants are finished. Reversing that list orders vertices so every edge points forward.

What is backtracking?

A DFS over the space of partial solutions: extend the current choice, recurse, and undo the choice when it leads to a dead end. Pruning invalid branches early makes it practical.