Depth First Search is a fundamental graph traversal algorithm where we explore a path as deep as possible before backtracking and trying another path.

Unlike BFS, which moves level by level, DFS dives deep into a branch, then unwinds and explores the next one.

In this chapter, we'll explore what DFS is, how it works step by step, and two ways to implement it in code.

Consider walking through a maze trying to reach the exit:

This is how DFS explores each path as deep as possible before backtracking.

DFS works on any structure that can be represented as nodes and edges like trees, tries, graphs and 2D grids. To prevent infinite loops, DFS marks nodes as visited so they aren't processed more than once.

Let's apply DFS to this graph starting from node A.

DFS can be implemented in two ways:

Both approaches achieve the same result, but they differ in how they manage backtracking and memory usage.

The recursive approach uses a boolean array to track visited nodes. For each call, mark the node as visited, process it, then recurse into each unvisited neighbor.

The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

This is because each node is processed exactly once and each edge is examined at most twice in an undirected graph (once from each endpoint) and exactly once in a directed graph.

The space complexity is O(V) since we are using a visited array of size V and in the worst case, recursion stack can grow up to the number of nodes.

For Example: If the graph is structured like a linked list, the recursion depth can reach O(V).

This can lead to stack overflow in large graphs.

An iterative approach is preferable when memory or stack overflow is a concern.

Let's see how to implement DFS iteratively using a stack:

The iterative version replaces the call stack with an explicit Stack and pushes neighbors in reverse order. Since a stack is last-in-first-out, reversing ensures the first neighbor is popped and processed first, matching the order the recursive version visits them.

Similar to the recursive approach, the time complexity is O(V + E) and the space complexity is O(V).

Time Complexity

DFS runs in O(V + E), where V is the number of vertices and E is the number of edges. The algorithm marks each vertex as visited and processes it exactly once, which accounts for the V term. For each vertex it visits, DFS scans through that vertex's neighbor list, so over the full traversal it examines every edge.

In an undirected graph each edge appears in the adjacency lists of both endpoints, so it gets examined at most twice. In a directed graph each edge appears in only the source vertex's list, so it gets examined once. Either way the edge work stays proportional to E, which gives the combined bound of O(V + E).

Space Complexity

DFS uses O(V) space. The visited array holds one boolean entry per vertex, so it grows linearly with V. On top of that, the recursive version consumes call stack frames and the iterative version consumes entries in the explicit stack. In the worst case both reach a depth of V.

A graph shaped like a single path, such as A to B to C and onward, forces DFS to descend through every vertex before it backtracks, so the stack holds V entries at its deepest point. Adding the visited array and the stack together still leaves the space at O(V).

Detecting cycles

DFS tracks the vertices currently on its active path, so when it reaches a vertex that already sits on that path, it has found a cycle. This fits DFS because the recursion naturally records the chain of vertices leading to the current one.

Topological sorting of a DAG

DFS produces a valid ordering of a directed acyclic graph by recording each vertex after it finishes exploring all of that vertex's descendants, then reversing the recorded order. The depth-first descent guarantees that dependencies appear before the vertices that rely on them.

Finding and counting connected components

Running DFS from an unvisited vertex reaches every vertex reachable from it, marking one full component in a single pass. Repeating this from each remaining unvisited vertex and counting how many times you start a new traversal gives the number of components.

Path finding between two nodes

DFS follows one branch all the way down before trying another, which lets it discover a route from a source to a target quickly when any valid path is acceptable. The backtracking unwinds dead ends and resumes from the last unexplored choice.

Flood fill and grid problems

Treating each cell as a node and its up, down, left, and right neighbors as edges lets DFS spread across a connected region, which solves problems like counting islands or filling a maze area. The deep exploration covers an entire region before moving on.

Backtracking

Problems such as generating subsets or permutations build a partial solution, recurse to extend it, then undo the last choice and try the next option. This explore-then-undo structure is DFS applied to the tree of possible decisions.