Depth-first search

Also known as: DFS

On this page 8

Depth-first search (DFS) is a graph and tree traversal algorithm that starts at a chosen vertex, follows one path as deep as possible, and only backtracks when it reaches a vertex with no unvisited neighbors. In programming and the study of algorithms, DFS is one of the two fundamental ways to explore a graph, alongside breadth-first search, and it underpins cycle detection, topological sorting, maze solving and the analysis of connected components.

The defining property of DFS is its last-in, first-out order: the most recently discovered vertex is always explored next. That order can be implemented with recursion, where the call stack keeps track of the path, or with an explicit stack data structure. On a graph with V vertices and E edges stored as an adjacency list, DFS runs in O(V + E) time, which makes it linear in the size of the input.

How depth-first search explores a graph

DFS explores a graph by repeatedly moving from the current vertex to an unvisited neighbor, marking each vertex as visited the first time it is reached. When every neighbor of the current vertex has already been visited, the algorithm returns to the previous vertex on the path and tries its remaining neighbors. The search ends when it has backtracked all the way to the starting vertex.

The visited set is essential. In a tree it can be omitted because there is exactly one path between any two nodes, but in a general graph that contains cycles, forgetting to mark vertices causes infinite loops or exponential re-exploration. Many implementations use three states, often called white, gray and black, to distinguish undiscovered vertices, vertices still on the active path, and fully finished vertices.

The following table summarizes the main steps of a recursive DFS and what each step contributes.

StepActionPurpose
DiscoverMark vertex as visited (gray)Prevents revisiting and loops
Pre-order hookRecord discovery time or process vertexSupports pre-order output
ExpandRecurse into each unvisited neighborMoves deeper along the path
FinishMark vertex as done (black)Signals subtree is complete
Post-order hookRecord finishing timeEnables topological sorting
Steps of a recursive depth-first search

The discovery and finishing times that DFS assigns are more than bookkeeping. They nest like parentheses, a result known as the parenthesis theorem, and they allow every edge to be classified as a tree edge, back edge, forward edge or cross edge. A back edge in a directed graph proves that the graph contains a cycle.

Recursive and iterative implementations

The recursive implementation is the shortest and most readable form: a function marks the current vertex and calls itself for each unvisited neighbor. Its weakness is the call stack limit. In languages such as Python, the default recursion limit is about one thousand frames, and in C or Java a path of hundreds of thousands of vertices can cause a stack overflow on a long chain-shaped graph.

The iterative implementation replaces the call stack with an explicit stack stored on the heap. A subtle point is that the naive version, which pushes all neighbors at once and marks vertices when they are popped, produces a valid depth-first order but not identical finishing times to the recursive version. When post-order matters, the stack must store each vertex together with an iterator over its neighbors.

The table below compares the two approaches on the properties that usually decide the choice.

PropertyRecursive DFSIterative DFS
Code lengthVery shortLonger, more bookkeeping
Memory locationCall stackHeap-allocated stack
Depth limitLanguage recursion limitAvailable memory only
Post-order correctnessNaturalRequires neighbor iterators
Typical useTeaching, small or balanced graphsProduction code, deep graphs
Recursive versus iterative DFS

DFS visits each vertex once and examines each edge once in a directed graph, or twice in an undirected graph, which gives a time complexity of O(V + E) with an adjacency list. With an adjacency matrix, scanning the neighbors of each vertex costs O(V), so the total becomes O(V squared) regardless of how many edges exist.

The space complexity is O(V) in the worst case, for the visited set and the stack. On trees, the stack holds at most one path, so memory use is proportional to the depth h rather than the width. This is the main reason DFS is preferred over breadth-first search on wide, shallow-to-moderate trees, where a queue of an entire level could be enormous.

DFS and breadth-first search (BFS) visit the same set of reachable vertices but in a different order, and that order determines which problems each one solves well. BFS uses a queue and explores vertices in rings of increasing distance, so it finds shortest paths in unweighted graphs. DFS gives no such guarantee: the first path it finds to a target may be far longer than necessary.

AlgorithmFrontier structureShortest path guaranteeTypical memory
Depth-first searchStack (LIFO)NoO(depth) on trees
Breadth-first searchQueue (FIFO)Yes, unweighted graphsO(width) on trees
Iterative deepening DFSStack with depth limitYes, unweighted graphsO(depth)
Dijkstra’s algorithmPriority queueYes, non-negative weightsO(V)
A* search algorithmPriority queue with heuristicYes, admissible heuristicOften large
How DFS differs from neighboring search algorithms

Iterative deepening depth-first search combines both worlds by running DFS repeatedly with an increasing depth limit. It keeps the low memory footprint of DFS while finding the shallowest solution, at the cost of re-exploring upper levels, an overhead that is modest when the branching factor is large.

Practical applications of DFS

DFS is the building block of many classic graph algorithms because its finishing order encodes structural information about the graph. The following decision table maps common problems to the DFS-based technique that solves them.

ProblemDFS-based techniqueKey idea
Cycle detection in directed graphsThree-color DFSA gray-to-gray edge is a back edge
Task or build orderingTopological sortReverse of finishing order
Strongly connected componentsTarjan or Kosaraju algorithmLow-link values or two passes
Network weak pointsBridges and articulation pointsCompare discovery and low-link times
Puzzles and constraint problemsBacktrackingUndo choices on dead ends
Maze generation and solvingRandomized DFSCarve or follow one corridor deeply
Problems solved with depth-first search

Backtracking, used for problems such as Sudoku, the N-queens puzzle or generating permutations, is DFS over an implicit state-space tree that is never stored in memory. Each recursive call represents a partial decision, and pruning cuts off branches that cannot lead to a valid solution, which is what keeps exponential search spaces tractable in practice.

Limitations and common mistakes

The most frequent problems with DFS come from misunderstanding what it guarantees and from implementation details that only appear on large inputs.

  • Assuming shortest paths: DFS finds a path, not the shortest one; use BFS or Dijkstra’s algorithm when distance matters.
  • Marking vertices too late: marking on pop instead of on push can add a vertex to the stack many times and inflate memory.
  • Ignoring recursion depth: a recursive DFS that passes unit tests can crash on a production graph with a long chain.
  • Infinite graphs: on unbounded state spaces, plain DFS can descend forever along one branch; a depth limit or iterative deepening is required.
  • Disconnected graphs: a single call explores only one component; a full traversal must restart DFS from every unvisited vertex.

Stripped to the essentials

Depth-first search is a way of exploring something made of connected points, such as a maze, a family tree or a network of web pages. You pick one path and keep walking forward as long as you can. When you hit a dead end, you step back to the last junction and try a path you have not taken yet.

Think of exploring a cave while unrolling a ball of string. The string lets you retrace your steps, and chalk marks on the walls stop you from walking the same tunnel twice. The key takeaway is simple: go deep first, then back up, and remember where you have already been.

Where it is applied

A build system for a large software project has to compile about 4,000 modules, and many of them depend on others. Before compiling anything, the tool must find an order in which every module is built after its dependencies, and it must reject the configuration if two modules depend on each other in a loop.

The build tool runs an iterative three-color DFS over the dependency graph. Whenever it meets an edge pointing to a module that is still gray, it reports a circular dependency with the exact chain of modules involved. Otherwise, it records each module when it finishes, and the reversed finishing list becomes the topological build order. Because the traversal is O(V + E), the analysis of roughly 4,000 modules and 25,000 dependency edges completes in milliseconds, and developers receive a precise error message instead of a stalled build.