Algorithms from zero
Depth-first search (DFS)
You know how to traverse a tree: pick a root, visit its children, then their children, in some order. Depth-first search (DFS) extends this to graphs. But there is a critical difference: a graph can have cycles. In a tree, there is exactly one path between any two nodes—once you visit a node, you never see it again. In a graph with cycles (A → B → A), you could loop forever, visiting the same vertices again and again. The solution is simple and crucial: track which vertices you have already visited and never visit them twice. This lesson teaches DFS in its two forms—recursive (natural and elegant) and iterative with an explicit stack (clearer about the order of exploration)—and shows why the visited set is essential.
After this lesson you can write DFS as a recursive function and as an iterative function with an explicit stack. You understand why a visited set is necessary for graphs (to prevent infinite loops on cycles), even though trees do not need one. You can trace DFS on a concrete graph with adjacency list and predict the order in which vertices are visited. You understand DFS’s time complexity O(V+E) and space complexity O(V), and you can identify when DFS is the tool to use: exploring all vertices reachable from a start vertex, or checking connectivity. Next lesson is breadth-first search (BFS), which explores layer by layer instead of going deep.
What is depth-first search?
Depth-first search (DFS) is a graph traversal that explores as far as possible along each edge before backtracking. It visits every vertex reachable from a starting vertex, in depth-first order.
Why DFS is different from tree traversal
In a tree, once you visit a node, there is no other path to it—it is impossible to visit it twice. In a graph with cycles, the same vertex can be reached via multiple paths. If you do not track visited vertices, you will loop forever:
Tree (no cycles): Graph (has cycle):
1 0
/ \ /|\
2 3 1 2 3
|/
1 ← cycle!In the tree, you visit 1, then 2 (once), then 3 (once). Done.
In the graph, starting from 0, you could go 0 → 1 → 1 → 1 … (infinite loop if you do not mark 1 as visited).
The fix: maintain a visited set—a set (or boolean array) recording which vertices you have already visited. Before visiting a vertex, check if it is in the visited set. If yes, skip it. If no, mark it visited and explore its neighbors.
Recursive DFS: simple and natural
The recursive approach mirrors tree traversal:
- Mark the current vertex as visited.
- For each neighbor of the current vertex:
- If the neighbor is not visited, recursively visit it.
That is it. The recursive call stack naturally manages the backtracking. When a recursive call returns, you automatically backtrack to explore other neighbors.
Iterative DFS: explicit stack
The recursive version is elegant but relies on the function call stack. An iterative version makes the stack explicit: push the starting vertex onto a stack, then:
- While the stack is not empty:
- Pop a vertex.
- If it is not visited, mark it visited and push all its unvisited neighbors onto the stack.
The order in which you push neighbors affects the order in which they are explored (LIFO from the stack).
Example graph
Let us use a simple directed graph with 4 vertices and 5 edges:
Adjacency list:
0: [1, 2]
1: [3]
2: [3]
3: [2]
Visual:
0 → 1
↓ ↓
2 → 3
↑ ↓
+---+Vertex 3 has an edge back to 2 (the cycle). Starting from vertex 0, DFS will visit 0, then 1 or 2 (depending on neighbor order), then 3, then back to 2 if not yet visited, or skip it if already visited.
Recursive DFS on the example
visited = {}
Start at 0.
- Mark 0 visited.
- Neighbor 1: not visited, recurse.
- Mark 1 visited.
- Neighbor 3: not visited, recurse.
- Mark 3 visited.
- Neighbor 2: not visited, recurse.
- Mark 2 visited.
- Neighbor 3: already visited, skip.
- Done with 2.
- Done with 3.
- Done with 1.
- Neighbor 2: already visited, skip.
- Done with 0.
Final visited order: 0 → 1 → 3 → 2.Recursive DFS
1
function dfsRecursive(vertex, adj, visited) {
2
// Mark this vertex as visited
3
visited.add(vertex);
4
5
// For each neighbor of this vertex
6
for (const neighbor of adj[vertex]) {
7
// If the neighbor is not visited, recurse
8
if (!visited.has(neighbor)) {
9
dfsRecursive(neighbor, adj, visited);
10
}
11
}
12
}
13
14
// To start DFS from a vertex:
15
const visited = new Set();
16
dfsRecursive(startVertex, adj, visited);
- L1 Takes a vertex, the adjacency list, and the visited set.
- L2 Mark this vertex visited (before exploring neighbors, not after).
- L5 Iterate all neighbors of the current vertex.
- L7 Only recurse into unvisited neighbors.
- L11 Call with a starting vertex and an empty visited set.
Iterative DFS with explicit stack
1
function dfsIterative(startVertex, adj) {
2
const visited = new Set();
3
const stack = [startVertex];
4
5
while (stack.length > 0) {
6
const vertex = stack.pop();
7
8
// Only process if not yet visited
9
if (!visited.has(vertex)) {
10
visited.add(vertex);
11
12
// Push unvisited neighbors onto the stack (in reverse order for consistent exploration)
13
for (let i = adj[vertex].length - 1; i >= 0; i--) {
14
const neighbor = adj[vertex][i];
15
if (!visited.has(neighbor)) {
16
stack.push(neighbor);
17
}
18
}
19
}
20
}
21
22
return visited;
23
}
- L1 Iterative version using an explicit stack.
- L2 Initialize a visited set.
- L3 Initialize the stack with the starting vertex.
- L5 While the stack is not empty, pop a vertex.
- L9 Check if this vertex has already been visited.
- L10 Mark it visited.
- L13 Push unvisited neighbors. We iterate in reverse order to maintain the same exploration order as recursive DFS.
- L20 Return the set of all visited vertices.
Running DFS on a graph
1
adj = { 0: [1, 2], 1: [3], 2: [3], 3: [2] };
2
visited = new Set();
3
dfsRecursive(0, adj, visited);
1
adj = { 0: [1, 2], 1: [3], 2: [3], 3: [2] };
2
stack = [0];
3
visited = new Set();
4
dfsIterative(0, adj);
Time complexity: O(V + E)
DFS visits each vertex once (V vertices) and each edge twice (once from each end). Actually, each edge is considered once in the direction of the adjacency list. For a directed graph, each edge is examined exactly once when we iterate the neighbors of its source vertex. Total work: V visits + E edge iterations = O(V + E).
Example: A graph with 5 vertices and 7 edges uses O(5 + 7) = O(12) operations—independent of whether the graph is sparse or dense.
Space complexity: O(V)
The visited set stores up to V entries (one per vertex): O(V).
The recursion stack (in recursive DFS) can go as deep as V in the worst case (a long chain: 0 → 1 → 2 → … → V-1): O(V).
The explicit stack (in iterative DFS) can hold up to V vertices at once (in a highly branching graph): O(V).
Total space: O(V).
Why the visited set is essential
Without the visited set, DFS on a cyclic graph will loop forever:
Example: 0 → 1 → 0 (a 2-cycle)
Without visited set:
Visit 0, go to 1.
Visit 1, go to 0.
Visit 0, go to 1.
Visit 1, go to 0.
... (infinite)
With visited set {0, 1}:
Visit 0, mark visited.
Go to 1 (not visited).
Visit 1, mark visited.
Go to 0 (already visited), skip.
Done.Trees have no cycles, so tree traversal does not strictly require a visited set (you will not re-enter a parent). But marking vertices as you visit them is still good practice and makes the code clearer.
In a graph with a cycle (e.g., 0 → 1 → 0), what happens if you run DFS without a visited set?
What is the time complexity of DFS on a graph with V vertices and E edges?
In recursive DFS, what data structure is used implicitly to manage the backtracking?
What is the space complexity of DFS, including the visited set and the stack (recursive or iterative)?
If you want DFS to explore neighbors in the exact same order for both recursive and iterative versions, how should you push neighbors onto the stack in the iterative version?
A graph has 6 vertices and 9 edges. What is the approximate time complexity O(V + E) in terms of the total number of vertex visits and edge examinations?
lesson.inset.undefined
Why DFS and not BFS? Both DFS and BFS explore all reachable vertices and have the same time complexity O(V + E). DFS is simpler to code (especially recursively) and uses less memory when the graph is very deep and narrow (a long chain). BFS is better when you need the shortest path (number of edges) or want to explore level-by-level. For now, DFS is your tool for exploring all reachable vertices and detecting cycles.
lesson.inset.undefined
Forgetting the visited set. It is tempting to omit the visited set on small examples or when you think “the graph has no cycles.” But cycles are easy to miss, and even acyclic graphs can have multiple paths to the same vertex (a DAG—directed acyclic graph). Always include a visited set. It is cheap (O(V) space) and saves you from infinite loops.
lesson.inset.undefined
Disconnected graphs. If a graph has multiple disconnected components, DFS from one vertex will only visit vertices reachable from that vertex. To visit all vertices in a disconnected graph, you must start a new DFS from an unvisited vertex. This is the foundation of the connected-components algorithm (coming in a later lesson).
lesson.inset.undefined
DFS for reachability. DFS answers the question: “Starting from vertex A, what vertices can I reach?” If you want to know whether there is a path from A to B, run DFS from A and check if B is in the visited set. If yes, there is a path. If no, there is no path.
Explain what DFS is, why the visited set is necessary for graphs (but not trees), and describe the time and space complexity.
Depth-first search (DFS) explores a graph by going as far as possible along each edge before backtracking. It uses a visited set to prevent revisiting vertices—essential for graphs with cycles, unlike trees.
Two implementations:
- Recursive DFS: Natural and simple; the call stack manages backtracking.
- Iterative DFS: Uses an explicit stack; clearer about state.
Both visit each vertex once and examine each edge once. Time: O(V + E). Space: O(V) for the visited set and stack.
Use DFS to explore all reachable vertices, detect connectivity, or check for paths. Next lesson: breadth-first search (BFS)—explore layer by layer instead of going deep.