Depth-First Search
Depth-first search commits: it picks a neighbour, follows it as far as it goes, and only backtracks when the path is exhausted. The recursion makes it three lines shorter than BFS and considerably harder to picture, because the interesting state lives in the call stack rather than in a container you can print.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
vector<vector<int> > adj;
vector<int> visited;
void dfs(int u) {
visited[u] = 1;
cout << u << ' ';
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i];
if (!visited[v]) dfs(v);
}
}
int main() {
int n = 6;
adj.assign(n, vector<int>());
visited.assign(n, 0);
adj[0].push_back(1); adj[0].push_back(2);
adj[1].push_back(3); adj[2].push_back(4);
adj[3].push_back(0); adj[4].push_back(5);
dfs(0);
return 0;
}The graph deliberately contains a cycle (3 back to 0) so the visited check is doing real work rather than being decoration.
How it works, step by step
The call stack is the path
At any moment, the sequence of active frames is exactly the path from the source to the node being explored. Backtracking is not a separate mechanism — it is what happens when a call returns and control resumes in the frame below.
Mark before you recurse
visited[u] = 1 is the first statement in the function, before any neighbour is followed. If it came after the loop, a cycle would send you straight back into an unmarked node and recurse forever.
The loop resumes where it left off
When dfs(v) returns, the for loop in u's frame continues with the next neighbour. That preserved loop index is the state that makes backtracking work, and it is stored implicitly in the stack frame rather than in any variable you wrote.
Visited prevents revisiting, not just cycles
Even in an acyclic graph, two different paths can reach the same node. Without the check you would explore that node's entire subgraph twice, turning linear work into exponential on a graph shaped like a diamond lattice.
One call per node, one scan per edge
Each node is entered exactly once thanks to the visited array, and each entry scans its adjacency list once. That is the O(V + E) bound, identical to BFS despite the completely different visit order.
Complexity
Each vertex is visited once and each edge examined once, but the space is the recursion depth, which on a long path-shaped graph is V — a graph with a million nodes in a chain will overflow the call stack before it finishes.
Common bugs
Marking visited after the recursive calls
Putting visited[u] = 1 below the loop means a cycle re-enters u while it is still unmarked, and the recursion never terminates. In DryRun you see the same node id reappearing on frame after frame as the stack grows — a far faster diagnosis than reading a stack trace after the crash.
Stack overflow on deep graphs
Recursive DFS uses one frame per node on the current path. A graph that is essentially a long chain — common in generated test data — needs V frames, and at a few hundred thousand nodes the process dies with no useful error. Convert to an explicit stack if depth can be large.
Confusing visited with on-the-current-path
For cycle detection in a directed graph, a single visited flag is not enough: a node reachable by two different paths is visited but not part of a cycle. You need three states — unvisited, in progress, and done — and only an edge back to an in-progress node indicates a cycle.
Forgetting disconnected components
One call to dfs(0) only reaches nodes connected to 0. If the graph has several components, you must loop over all vertices and start a fresh DFS from any that are still unvisited. Silently missing half the graph is easy when your test input happens to be connected.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
How does depth-first search work?
It starts at a source node, marks it visited, and recursively explores the first unvisited neighbour as deeply as possible before backtracking to try the next one. The recursion's call stack holds the current path, and returning from a call is exactly what backtracking means.
Why does DFS need a visited array?
To stop it revisiting nodes. In a cyclic graph, following edges without checking leads back to a node already on the path and the recursion never terminates. Even in an acyclic graph, the array prevents re-exploring a node reachable by multiple paths, which can otherwise turn linear work into exponential.
Should DFS be recursive or iterative?
Recursive is shorter and clearer, and it is fine when the graph's longest path is modest. Use an explicit stack when depth can reach into the hundreds of thousands, since each recursive call consumes a stack frame and the default stack will overflow. The two produce the same set of visited nodes but not necessarily the same visit order.
When should I use DFS instead of BFS?
For cycle detection, topological sorting, finding connected components, and any backtracking search over configurations. DFS also uses less memory on wide graphs, since it stores only the current path rather than an entire frontier. Use BFS instead whenever you need shortest paths in an unweighted graph.