Depth-First Search is the other half of the classic traversal pair alongside BFS, and honestly it’s the one I reach for more often in practice. Instead of expanding outward in layers, DFS commits to a path and follows it as deep as possible before backtracking. That “go deep first, backtrack when stuck” behavior makes it a natural fit for problems involving structure discovery — cycle detection, topological ordering, connectivity, and pathfinding in mazes where I don’t care about shortest distance but do care about exploring exhaustively.
History and Background
DFS has roots that go back further than most people expect. It was formalized as a maze-traversal strategy in the 19th century by mathematician Charles Pierre Trémaux, whose method for solving mazes without getting lost is essentially DFS with backtracking. In computer science, DFS was popularized and rigorously analyzed by Robert Tarjan in the early 1970s, whose work applying DFS to problems like strongly connected components and biconnectivity turned it from a simple traversal trick into one of the most powerful tools in graph algorithm design. It’s now a cornerstone of algorithms education and appears in essentially every algorithms textbook, most notably CLRS.
Problem Statement
Given a graph G = (V, E) and a starting vertex (or the need to cover all vertices even in a disconnected graph), the goal is to visit every reachable vertex exactly once, in a way that fully explores each branch before backtracking, and to record useful structural information along the way such as discovery/finish times, parent relationships, and edge classifications.
Core Concepts
- Discovery time: The step at which a vertex is first encountered.
- Finish time: The step at which all of a vertex’s descendants have been fully explored.
- Tree edge: An edge that leads to discovering a new vertex.
- Back edge: An edge to an ancestor in the current DFS tree — the signature of a cycle in a directed graph.
- Forward edge: An edge to a descendant already discovered via another path.
- Cross edge: An edge to a vertex that is neither ancestor nor descendant.
- Recursion stack (call stack): The implicit or explicit stack that tracks the current path from the root.
How It Works
- Pick a starting vertex, mark it visited, and record its discovery time.
- Look at its neighbors one at a time. For the first unvisited neighbor, recurse into it (go deeper).
- Continue this recursive descent until reaching a vertex with no unvisited neighbors.
- Backtrack to the previous vertex, record its finish time, and try its next unvisited neighbor.
- Repeat until every vertex reachable from the start has been visited; if the graph is disconnected, restart the process from any remaining unvisited vertex.
Working Principle
DFS relies on a Last-In-First-Out (LIFO) structure — either the actual call stack through recursion, or an explicit stack if implemented iteratively. This is what produces the “dive deep, then backtrack” behavior: the most recently discovered vertex is always the next one explored. This ordering is precisely what makes DFS so good at revealing structural properties like cycles (a back edge appears exactly when I encounter a vertex that’s still on the current stack) and hierarchical relationships (the parenthesis structure of discovery/finish times mirrors nested scopes).
Mathematical Foundation
The parenthesis theorem is the core mathematical result behind DFS: for any two vertices u and v, exactly one of the following holds:
$$[d[u], f[u]] \text{ and } [d[v], f[v]] \text{ are entirely disjoint}$$
$$[d[u], f[u]] \text{ is nested entirely within } [d[v], f[v]] \text{ (v is an ancestor of u)}$$
$$[d[v], f[v]] \text{ is nested entirely within } [d[u], f[u]] \text{ (u is an ancestor of v)}$$
where d[x] and f[x] denote the discovery and finish times of vertex x. This nesting property is what enables correct classification of edges and underlies algorithms like topological sort and SCC detection. The running time is:
$$T(V, E) = O(V + E)$$
since each vertex is visited once and each edge examined once (or twice in an undirected graph).
Diagrams
flowchart TD
A[Start DFS at vertex u] --> B[Mark u visited, record discovery time]
B --> C{Unvisited neighbor v exists?}
C -- Yes --> D[Recurse into v]
D --> C
C -- No --> E[Record finish time for u, backtrack]
E --> F{More vertices unvisited in graph?}
F -- Yes --> A
F -- No --> G[Done]Pseudocode
DFS(G):
for each vertex u in G.V:
visited[u] = false
parent[u] = NIL
time = 0
for each vertex u in G.V:
if visited[u] == false:
DFS-VISIT(G, u)
DFS-VISIT(G, u):
time = time + 1
discovery[u] = time
visited[u] = true
for each v in G.adj[u]:
if visited[v] == false:
parent[v] = u
DFS-VISIT(G, v)
time = time + 1
finish[u] = time
Step-by-Step Example
Using this directed graph:
1 -> 2
1 -> 3
2 -> 4
3 -> 4
4 -> 5
Starting DFS from vertex 1:
- Visit 1 (discovery time 1).
- From 1, go to 2 (discovery time 2).
- From 2, go to 4 (discovery time 3).
- From 4, go to 5 (discovery time 4). 5 has no unvisited neighbors, finish time 5.
- Backtrack to 4. No more unvisited neighbors, finish time 6.
- Backtrack to 2. No more unvisited neighbors, finish time 7.
- Backtrack to 1. Try neighbor 3 (discovery time 8). Its neighbor 4 is already visited, so finish time 9 for vertex 3.
- Backtrack to 1. No more neighbors, finish time 10.
Final traversal order: 1, 2, 4, 5, 3.
Time Complexity
- Best, Average, and Worst Case: O(V + E) using an adjacency list, since every vertex is visited exactly once and every edge is examined exactly once (directed) or twice (undirected).
- With an adjacency matrix, this rises to O(V²) because scanning for neighbors of each vertex takes O(V) regardless of actual edge count.
Space Complexity
- O(V) for the visited array and parent/discovery/finish time arrays.
- O(V) worst case for the recursion stack (or explicit stack in iterative form), which happens in a graph shaped like a single long chain.
- Graph storage itself adds O(V + E) for an adjacency list.
Correctness Analysis
DFS’s correctness follows from a simple inductive argument: DFS-VISIT is only called on unvisited vertices, and it’s marked visited immediately upon entry, which prevents infinite loops even in cyclic graphs. Because the outer loop tries every vertex as a starting point if it hasn’t been visited yet, every vertex in the graph — even in disconnected components — is guaranteed to be visited exactly once. The parenthesis theorem, provable by induction on discovery/finish time ordering, guarantees the well-formed nesting property that many derivative algorithms (like SCC and topological sort) depend on.
Advantages
- Very memory-efficient for deep, narrow graphs compared to BFS.
- Naturally reveals structural information (cycles, articulation points, bridges, connected components) that’s harder to extract from BFS.
- Forms the foundation for many other algorithms: topological sort, SCC (Tarjan’s and Kosaraju’s algorithms), cycle detection, and solving constraint satisfaction problems via backtracking.
- Simple, elegant recursive implementation.
Disadvantages
- Does not guarantee shortest paths, even in unweighted graphs.
- Can hit stack overflow on very deep graphs if implemented recursively without care.
- Exploration order can be unpredictable/non-intuitive since it depends on the order neighbors are stored.
- Not ideal for finding the closest solution to a search problem, since it might explore a long irrelevant branch before nearby vertices.
Applications
- Cycle detection in directed and undirected graphs.
- Topological sorting of a DAG.
- Finding strongly connected components (Tarjan’s and Kosaraju’s algorithms).
- Solving maze and puzzle problems, and backtracking search (like Sudoku solvers or N-Queens).
- Detecting connected components and articulation points/bridges in networks.
- Compiler dependency resolution and build systems.
- Generating and solving mazes procedurally in games.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct {
int adj[MAX_VERTICES][MAX_VERTICES];
int numVertices;
} Graph;
int visited[MAX_VERTICES];
int discoveryTime[MAX_VERTICES];
int finishTime[MAX_VERTICES];
int timer = 0;
void initGraph(Graph *g, int n) {
g->numVertices = n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g->adj[i][j] = 0;
}
void addEdge(Graph *g, int u, int v) {
g->adj[u][v] = 1; /* directed edge; add g->adj[v][u]=1 for undirected */
}
void dfsVisit(Graph *g, int u) {
visited[u] = 1;
discoveryTime[u] = ++timer;
printf("Visiting: %d (time %d)\n", u, discoveryTime[u]);
for (int v = 0; v < g->numVertices; v++) {
if (g->adj[u][v] == 1 && !visited[v]) {
dfsVisit(g, v);
}
}
finishTime[u] = ++timer;
printf("Finished: %d (time %d)\n", u, finishTime[u]);
}
void dfs(Graph *g) {
for (int i = 0; i < g->numVertices; i++) {
visited[i] = 0;
}
timer = 0;
for (int u = 0; u < g->numVertices; u++) {
if (!visited[u]) {
dfsVisit(g, u);
}
}
}
int main(void) {
Graph g;
initGraph(&g, 5);
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 3);
addEdge(&g, 2, 3);
addEdge(&g, 3, 4);
dfs(&g);
return 0;
}
Sample Input and Output
Input: Directed graph with edges (0,1), (0,2), (1,3), (2,3), (3,4).
Output:
Visiting: 0 (time 1)
Visiting: 1 (time 2)
Visiting: 3 (time 3)
Visiting: 4 (time 4)
Finished: 4 (time 5)
Finished: 3 (time 6)
Finished: 1 (time 7)
Visiting: 2 (time 8)
Finished: 2 (time 9)
Finished: 0 (time 10)
Optimization Techniques
- Iterative DFS with an explicit stack: Avoids recursion depth limits and potential stack overflow on very large or deep graphs.
- Adjacency list over matrix: Cuts traversal cost from O(V²) to O(V + E) on sparse graphs.
- Early termination: If I only need to know reachability or detect a specific target, I can stop as soon as the target is found instead of exhaustively finishing the traversal.
- Iterative deepening DFS (IDDFS): Combines DFS’s low memory footprint with BFS-like level-bounded exploration, useful in state-space search with unknown depth.
- Tail-call-style loop unrolling: In performance-critical C code, converting recursive DFS to a loop with a manual stack avoids function call overhead.
Common Mistakes
- Forgetting to check for already-visited vertices before recursing, which causes infinite loops on cyclic graphs.
- Confusing back edges with cross/forward edges when implementing cycle detection — checking only “already visited” isn’t enough for directed graphs; I need to check if a vertex is still on the current recursion stack.
- Not handling disconnected graphs, forgetting to loop over all vertices as potential DFS-VISIT starting points.
- Recursive stack overflow on graphs with long chains, especially in languages/environments with small default stack sizes.
- Assuming DFS traversal order is unique — it actually depends on how neighbor lists are ordered.
Further Reading
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 3rd/4th Edition, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146-160.
- GeeksforGeeks, Depth First Search: https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
- Stanford CS161 Lecture Notes on Graph Search: https://web.stanford.edu/class/cs161/
- Visualgo, Graph Traversal visualization: https://visualgo.net/en/dfsbfs
