DFS (Depth-First Search)
Depth-First Search dives as deep as possible along each branch before backtracking. It uses a stack (LIFO) — either explicitly or via recursion's call stack — to track which node to explore next. DFS is the foundation for cycle detection, topological sorting, and many other graph algorithms.
How DFS Works
DFS starts at a chosen source node and explores as far as possible along each branch before backtracking. Unlike BFS, which explores level by level, DFS goes deep first.
The iterative algorithm proceeds as follows:
- Push the starting node onto the stack.
- While the stack is not empty, pop the top node.
- If the popped node has not been visited, mark it as visited.
- For each unvisited neighbor, push it onto the stack.
- Repeat until the stack is empty.
The recursive version replaces the explicit stack with the call stack: for each unvisited neighbor of the current node, recursively call DFS. The base case is when a node has no unvisited neighbors.
Key insight: Because DFS explores one entire branch before moving to the next, it is well-suited for problems that require exhaustive exploration, such as finding connected components, detecting cycles, computing strongly connected components (Tarjan's/Kosaraju's), and generating topological orderings of directed acyclic graphs (DAGs).
Interactive Visualization
Watch DFS traverse the same graph used in the BFS topic. White nodes are unvisited, yellow nodes are on the stack, and green nodes have been fully visited. The stack contents are shown vertically on the right.
Code Implementation
Below are both the recursive and iterative implementations of DFS. The recursive version is more concise, while the iterative version avoids stack overflow on very deep graphs.
def dfs_recursive(graph, node, visited=None):
"""Perform DFS recursively from the given node."""
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited
def dfs_iterative(graph, start):
"""Perform DFS iteratively using an explicit stack."""
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop() # Pop from top
if node in visited:
continue
visited.add(node)
order.append(node)
# Push neighbors in reverse order so first neighbor is on top
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return order
# Example usage
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5, 6],
3: [1],
4: [1],
5: [2],
6: [2]
}
print(dfs_iterative(graph, 0)) # Output: [0, 1, 3, 4, 2, 5, 6]
import java.util.*;
public class DFS {
/** Recursive DFS */
public static void dfsRecursive(Map<Integer, List<Integer>> graph,
int node, Set<Integer> visited) {
visited.add(node);
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
dfsRecursive(graph, neighbor, visited);
}
}
}
/** Iterative DFS using an explicit stack */
public static List<Integer> dfsIterative(Map<Integer, List<Integer>> graph,
int start) {
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
List<Integer> order = new ArrayList<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop(); // Pop from top
if (visited.contains(node)) continue;
visited.add(node);
order.add(node);
List<Integer> neighbors = graph.get(node);
// Push in reverse so first neighbor is on top
for (int i = neighbors.size() - 1; i >= 0; i--) {
if (!visited.contains(neighbors.get(i))) {
stack.push(neighbors.get(i));
}
}
}
return order;
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(0, 3, 4));
graph.put(2, Arrays.asList(0, 5, 6));
graph.put(3, Arrays.asList(1));
graph.put(4, Arrays.asList(1));
graph.put(5, Arrays.asList(2));
graph.put(6, Arrays.asList(2));
System.out.println(dfsIterative(graph, 0));
// Output: [0, 1, 3, 4, 2, 5, 6]
}
}
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>
using namespace std;
/** Recursive DFS */
void dfsRecursive(const vector<vector<int>>& graph, int node,
unordered_set<int>& visited) {
visited.insert(node);
cout << node << " ";
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
dfsRecursive(graph, neighbor, visited);
}
}
}
/** Iterative DFS using an explicit stack */
vector<int> dfsIterative(const vector<vector<int>>& graph, int start) {
unordered_set<int> visited;
stack<int> stk;
vector<int> order;
stk.push(start);
while (!stk.empty()) {
int node = stk.top(); // Pop from top
stk.pop();
if (visited.count(node)) continue;
visited.insert(node);
order.push_back(node);
// Push neighbors in reverse order so first neighbor is on top
for (int i = graph[node].size() - 1; i >= 0; i--) {
if (!visited.count(graph[node][i])) {
stk.push(graph[node][i]);
}
}
}
return order;
}
int main() {
vector<vector<int>> graph = {
{1, 2}, // 0
{0, 3, 4}, // 1
{0, 5, 6}, // 2
{1}, // 3
{1}, // 4
{2}, // 5
{2} // 6
};
vector<int> result = dfsIterative(graph, 0);
for (int node : result) {
cout << node << " ";
}
// Output: 0 1 3 4 2 5 6
cout << endl;
return 0;
}
Complexity Analysis
Like BFS, DFS visits every vertex and edge exactly once. The main difference is the order of exploration, not the asymptotic cost. However, the recursive version may use O(V) stack space in the worst case (e.g., a linear chain graph), which can cause a stack overflow for very deep graphs.
| Metric | Complexity | Description |
|---|---|---|
| Time | O(V + E) | Each vertex is visited once; each edge is examined once |
| Space | O(V) | The stack (explicit or call stack) holds at most V entries |
DFS vs BFS: Both run in O(V+E) time, but DFS uses less memory on wide graphs (many neighbors per node) while BFS uses less memory on deep, narrow graphs. DFS does not guarantee shortest paths, but it is essential for topological sorting, cycle detection, finding bridges/articulation points, and solving maze/backtracking problems.
Quiz
Test your understanding of DFS with these questions.
Q1. Which data structure does DFS use to determine the next node to visit?
Q2. Which of the following is NOT a common application of DFS?
Q3. Given the graph {0:[1,2], 1:[0,3,4], 2:[0,5,6], 3:[1], 4:[1], 5:[2], 6:[2]}, what is a valid DFS traversal order starting from node 0 (visiting neighbors in listed order)?
Q4. What is the worst-case space complexity of recursive DFS on a graph with V vertices?
Q5. How does DFS differ from BFS in terms of traversal order?