I think of depth-first search as the algorithm that explores a graph the way I might navigate a maze by always choosing to go as deep as possible down one path before backtracking. Instead of exploring outward in layers like breadth-first search, DFS commits to a single path, following it as far as it can go, and only turns back when it hits a dead end. This exploration strategy makes DFS the natural fit for problems involving backtracking, cycle detection, topological ordering, and exploring all possible configurations of a search space — it is one of the two traversal strategies I reach for constantly when working with graphs and trees.
History and Background
Depth-first search has roots stretching back to 19th-century maze-solving techniques, most notably formalized by French mathematician Charles Pierre Trémaux, whose maze-traversal algorithm from the 1880s is considered one of the earliest documented depth-first strategies. In computer science, DFS was rigorously formalized and analyzed as a fundamental graph algorithm during the 1970s, most influentially by Robert Tarjan, whose work using DFS to compute strongly connected components (in 1972) and other structural graph properties demonstrated just how powerful the technique could be beyond simple traversal. DFS’s connection to backtracking search also made it foundational to early artificial intelligence and constraint-satisfaction research.
Problem Statement
I need a systematic way to explore every reachable node in a graph or tree, particularly in situations where I need to explore paths fully before considering alternatives — such as detecting cycles, finding connected components, performing topological sorts, or solving problems like maze generation and puzzle solving that require deep, path-committed exploration rather than broad, layer-by-layer exploration.
Core Concepts
- Stack (explicit or via recursion): DFS relies on a last-in-first-out structure, either an explicit stack or the implicit call stack of recursive function calls, to remember which nodes to backtrack to.
- Visited set: tracks which nodes have already been explored, preventing infinite loops in cyclic graphs.
- Backtracking: the process of returning to a previous node once all paths from the current node have been exhausted.
- DFS tree/forest: the structure formed by the traversal, made of tree edges (used to discover new nodes), back edges (pointing to ancestors, indicating cycles), and cross/forward edges depending on the graph’s directedness.
- Discovery and finish times: timestamps recorded when a node is first visited and when the DFS finishes exploring all its descendants, which are crucial for algorithms like topological sorting and strongly connected component detection.
How It Works
I carry out DFS through these steps:
- I start at a source node, mark it as visited, and process it.
- I look at its neighbors, and for the first unvisited neighbor I find, I recursively (or via an explicit stack) dive into that neighbor, repeating this same process.
- When I reach a node with no unvisited neighbors, I backtrack to the previous node in the path.
- I continue exploring any remaining unvisited neighbors of that previous node, repeating the dive-and-backtrack process until every node reachable from the source has been visited.
Working Principle
The mechanism DFS relies on is depth-first commitment: rather than exploring all neighbors of a node before moving further, I immediately commit to exploring one neighbor fully — descending into its subtree entirely — before even glancing at the node’s other neighbors. This is naturally expressed through recursion, where each recursive call represents “going deeper,” and the call stack automatically remembers the path I took, allowing me to backtrack correctly once a branch is exhausted. This depth-first commitment is exactly what makes DFS so effective for problems involving exhaustive search, since it naturally explores entire branches (and can prune them) before considering alternatives.
Mathematical Foundation
For a graph with V vertices and E edges, DFS visits every vertex once and examines every edge once (or twice for undirected graphs), giving:
$$T(V, E) = O(V + E)$$
For recursive implementations, the maximum depth of recursion corresponds to the longest path explored, which in the worst case (a graph shaped like a single long chain) can be:
$$\text{recursion depth} = O(V)$$
DFS discovery and finish times can be used to classify edges formally. For a directed graph, an edge (u, v) is classified based on the relationship between the discovery time $d[u]$, $d[v]$ and finish time $f[u]$, $f[v]$:
$$\text{Tree edge: } v \text{ is undiscovered when } (u,v) \text{ is explored}$$ $$\text{Back edge: } d[u] > d[v] \text{ and } f[v] \text{ is not yet set (v is an ancestor of u)}$$
This classification underlies algorithms like cycle detection (a back edge implies a cycle) and topological sorting (reverse of finish-time order).
Diagrams
flowchart TD
A[Start: source node] --> B[Mark node visited, process it]
B --> C{Any unvisited neighbor?}
C -->|Yes| D[Recurse into that neighbor]
D --> B
C -->|No| E[Backtrack to previous node]
E --> F{Backtrack point has more unvisited neighbors?}
F -->|Yes| C
F -->|No| G{Any node left unvisited overall?}
G -->|Yes| E
G -->|No| H[Output: All reachable nodes visited]
Pseudocode
DFS(Graph, source)
create empty set visited
DFS-VISIT(Graph, source, visited)
DFS-VISIT(Graph, node, visited)
mark node as visited
process(node)
for each neighbor in Graph.adjacent(node)
if neighbor is not visited
DFS-VISIT(Graph, neighbor, visited)
Iterative version using an explicit stack:
DFS-ITERATIVE(Graph, source)
create empty stack S
create empty set visited
push source onto S
while S is not empty
node = pop S
if node is not visited
mark node as visited
process(node)
for each neighbor in Graph.adjacent(node)
if neighbor is not visited
push neighbor onto S
Step-by-Step Example
I will run DFS on this graph starting at node S: S — A, S — B, A — C, A — D, B — E, C — F
Step 1: Visit S, mark visited, process it. Neighbors: A, B.
Step 2: Dive into A (first unvisited neighbor of S). Mark visited, process it. Neighbors: C, D.
Step 3: Dive into C (first unvisited neighbor of A). Mark visited, process it. Neighbor: F.
Step 4: Dive into F (only neighbor of C). Mark visited, process it. No unvisited neighbors — backtrack to C.
Step 5: C has no more unvisited neighbors — backtrack to A.
Step 6: A has an unvisited neighbor D — dive into D. Mark visited, process it. No unvisited neighbors — backtrack to A.
Step 7: A has no more unvisited neighbors — backtrack to S.
Step 8: S has an unvisited neighbor B — dive into B. Mark visited, process it. Neighbor: E.
Step 9: Dive into E (only neighbor of B). Mark visited, process it. No unvisited neighbors — backtrack to B, then S. No more unvisited neighbors anywhere.
Traversal order: S, A, C, F, D, B, E
Time Complexity
- Best case: O(V + E) — DFS must still visit every reachable vertex and traverse every edge at least once.
- Average case: O(V + E) — this holds regardless of graph shape, since every vertex and edge is processed a constant number of times.
- Worst case: O(V + E) — even densely connected or deeply chained graphs stay within this bound.
Space Complexity
DFS requires O(V) space for the visited set. For the recursive implementation, the call stack can grow to O(V) in the worst case (a graph shaped like a single long path), and the same bound applies to the explicit stack in an iterative implementation. Overall space complexity is O(V).
Correctness Analysis
I prove DFS’s correctness by showing it visits every node reachable from the source exactly once. Termination follows from the fact that each node is marked visited before its neighbors are explored, and the visited check prevents re-processing, so the recursion (or stack) must eventually run out of unvisited neighbors to explore. Completeness follows by contradiction: if some node reachable from the source were never visited, then consider the shortest path from the source to that node — every node along that path must have been visited (since DFS explores all edges of every visited node), which would mean the target node itself must have been discovered as a neighbor of the last visited node on that path, contradicting the assumption that it was never visited. Therefore, every reachable node is guaranteed to be visited.
Advantages
- Uses less memory than BFS in many cases, especially for graphs that are deep and narrow rather than wide.
- Naturally suited for problems requiring backtracking, such as puzzle solving, maze generation, and constraint satisfaction.
- Forms the basis for many advanced graph algorithms, including topological sorting, cycle detection, and finding strongly connected components (Tarjan’s and Kosaraju’s algorithms).
- Simple to implement recursively, with the call stack handling backtracking automatically.
Disadvantages
- Does not guarantee the shortest path in unweighted graphs — unlike BFS, it can find a much longer path to a node before finding a shorter one.
- Can hit stack overflow issues in very deep graphs when implemented recursively, requiring an iterative version with an explicit stack for safety.
- Less intuitive than BFS for problems specifically about “distance” or “closeness,” since depth-first exploration order does not correlate with shortest-path distance.
- In infinite or very large state spaces (such as some AI search problems), DFS can get stuck exploring a single unproductive branch indefinitely unless a depth limit is imposed.
Applications
- Cycle detection in graphs, using the presence of back edges during traversal.
- Topological sorting of directed acyclic graphs, used in task scheduling and build systems (like determining compilation order).
- Finding connected components and strongly connected components in graphs, important in network analysis and compiler optimization.
- Solving puzzles and games that require exhaustive search with backtracking, such as Sudoku solvers, N-Queens, and maze generation.
- Used in compilers for analyzing dependency graphs and in file system traversal for recursively exploring directory structures.
Implementation in C
#include <stdio.h>
#define MAX_VERTICES 100
// Simple adjacency list representation
int adjList[MAX_VERTICES][MAX_VERTICES];
int adjCount[MAX_VERTICES];
int visited[MAX_VERTICES];
// Recursive DFS visit function
void dfsVisit(int node) {
visited[node] = 1;
printf("%d ", node);
for (int i = 0; i < adjCount[node]; i++) {
int neighbor = adjList[node][i];
if (!visited[neighbor]) {
dfsVisit(neighbor);
}
}
}
// DFS traversal starting from a given source vertex
void dfs(int source, int numVertices) {
for (int i = 0; i < numVertices; i++) visited[i] = 0;
printf("DFS traversal order: ");
dfsVisit(source);
printf("\n");
}
// Add an undirected edge between u and v
void addEdge(int u, int v) {
adjList[u][adjCount[u]++] = v;
adjList[v][adjCount[v]++] = u;
}
int main() {
int numVertices = 6; // S=0, A=1, B=2, C=3, D=4, E=5
addEdge(0, 1); // S-A
addEdge(0, 2); // S-B
addEdge(1, 3); // A-C
addEdge(1, 4); // A-D
addEdge(2, 5); // B-E
dfs(0, numVertices);
return 0;
}
Sample Input and Output
Input: Graph with edges S-A, S-B, A-C, A-D, B-E, starting DFS from S (vertex 0)
Output: DFS traversal order: 0 1 3 4 2 5
(In this indexed example, node C (index 3) is visited right after A because it comes first in the adjacency list order used in the code.)
Optimization Techniques
- I convert recursive DFS to an iterative version using an explicit stack when working with very deep graphs, to avoid stack overflow from excessive recursion depth.
- I use DFS with memoization (storing intermediate results) when the same subproblems are revisited repeatedly, common in dynamic programming problems modeled as graph traversal.
- I apply iterative deepening DFS (running DFS repeatedly with increasing depth limits) when I need DFS’s low memory footprint but also want a guarantee similar to BFS’s shortest-path property, common in AI search.
- I track discovery and finish times during traversal when the goal is more than simple visitation, such as building a topological order or detecting cycles efficiently.
Common Mistakes
- Forgetting to mark a node as visited before recursing into its neighbors, which can cause infinite recursion in graphs with cycles.
- Confusing DFS’s traversal order with a shortest-path guarantee, leading to incorrect assumptions in pathfinding problems where BFS should be used instead.
- Not handling disconnected graphs — a single DFS call only reaches nodes connected to the source, requiring repeated DFS calls across all unvisited nodes to cover the entire graph.
- Using recursion without considering stack depth limits, which can cause a stack overflow on very large or deeply nested graphs.
- Misclassifying edges (tree vs. back vs. cross) when implementing algorithms that depend on DFS edge types, such as cycle detection in directed graphs.
Further Reading
- Tarjan, Robert, “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing, 1972: https://epubs.siam.org/doi/10.1137/0201010
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, “Depth First Search or DFS for a Graph”: https://www.geeksforgeeks.org/dsa/depth-first-search-or-dfs-for-a-graph/
- Visualgo, Graph Traversal Visualizations: https://visualgo.net/en/dfsbfs
