Depth-First Search
Depth-First Search (DFS) dives down a single path as far as it can go before hitting a dead end and backtracking.
Dive, Then Backtrack
Depth-first search explores by committing to one path and following it as far as it goes, only backtracking when it reaches a vertex with no unvisited neighbours. Where BFS spreads outward evenly, DFS plunges.
The mechanism is a stack, and usually it is the call stack via recursion: visit a vertex, mark it, and recurse into each unvisited neighbour in turn. The implicit stack of pending calls is what enables the backtracking — returning from a call resumes the previous vertex exactly where it left off.
Written iteratively, the same behaviour needs an explicit stack: push the source, then pop a vertex, mark it, and push its unvisited neighbours. One detail differs from the recursive form and is worth stating — because a stack reverses order, children must be pushed in reverse for the traversal order to match the recursive version. Implementations that ignore this are still correct DFS, just visiting in a different sequence.
The complexity is O(V + E) on an adjacency list — each vertex is visited once and each edge examined once, or twice in an undirected graph. On an adjacency matrix it becomes O(V²) for the same reason BFS does.
The relationship to BFS is exact: the algorithms differ only in the container. Swap the queue for a stack and BFS becomes DFS. What differs is which questions each answers well, and that follows entirely from the order the vertices come out.
- Follow one path to its end, then backtrack to the last branch
- The call stack is the usual implementation of the stack
- Iterative DFS pushes children in reverse to match recursive order
- O(V + E) on an adjacency list, like BFS
Entry, Exit, and What They Reveal
DFS's real power is not the traversal order but the timing information it produces. Recording when each vertex is entered and when it is exited — the discovery and finish times — turns a traversal into a structural analysis.
The key property is nesting: if v is discovered while u is still on the stack, then v is finished before u is. So the intervals [entry, exit] of any two vertices are either disjoint or nested, never partially overlapping. This is the parenthesis theorem, and nesting means exactly that v is a descendant of u in the DFS tree.
That single fact lets every edge be classified. A tree edge leads to an undiscovered vertex and becomes part of the DFS tree. A back edge leads to a vertex still on the stack — an ancestor — and therefore closes a cycle. A forward edge leads to an already-finished descendant, and a cross edge to a finished vertex in an unrelated subtree.
Back edges are the important case: a directed graph has a cycle if and only if a DFS finds a back edge. This is the cleanest cycle detection available and requires only tracking which vertices are currently on the stack.
That tracking needs three states, not two, and conflating them is the standard bug. White means undiscovered, grey means on the stack right now, black means fully finished. Reaching a grey vertex is a back edge and a cycle; reaching a black vertex is fine, being merely a second route into a completed region. A plain visited boolean cannot tell these apart and reports cycles on perfectly acyclic graphs.
The finish order carries information too. A vertex finishes only after everything reachable from it has finished, so reversing the finish order gives a topological sort of a DAG. And running DFS twice — once on the graph, once on its transpose in decreasing finish order — yields the strongly connected components, which is Kosaraju's algorithm.
| Edge type | Leads to | Means |
|---|---|---|
| Tree | An undiscovered vertex | Part of the DFS tree |
| Back | A grey vertex — still on the stack | A cycle |
| Forward | A black descendant | A shortcut within the subtree |
| Cross | A black vertex elsewhere | Between unrelated subtrees |
- Entry–exit intervals are nested or disjoint, never overlapping
- A back edge reaches a vertex still on the stack — that is a cycle
- Three colours are required; a visited flag gives false positives
- Reversed finish order is a topological sort
The Cost of Depth
DFS uses O(depth) space, against BFS's O(width). On a deep, narrow graph that is a decisive advantage; on a shallow, wide one it is the reverse.
But recursion depth is also DFS's practical failure mode. Each recursive call consumes a stack frame, and the stack is a fixed region of a few megabytes. A graph shaped as a long chain — or a degenerate tree — of a million vertices needs a million frames and overflows the stack, terminating the program.
The threshold varies by language and frame size, but a few thousand to a few hundred thousand frames is typical. Python's default limit is 1000, deliberately low, raising RecursionError rather than crashing.
The remedy is the iterative form with an explicit stack, which moves the frames onto the heap where megabytes are cheap. The translation is mechanical for pre-order work but genuinely awkward when work must happen on exit, since a popped vertex cannot simply be finished — its children may not be done. The usual solutions are to push each vertex twice with a marker, or to push a state flag alongside each vertex.
This is worth flagging in an interview: mentioning that recursive DFS risks stack overflow on adversarial input, and that an iterative version exists, is the difference between a correct answer and a complete one.
Two further correctness points apply to both forms. Restart from every unvisited vertex when the graph may be disconnected, or entire components are silently skipped. And in an undirected graph, avoid mistaking the edge you arrived on for a cycle — pass the parent vertex down and skip it, since every undirected edge appears in both adjacency lists and would otherwise register as a back edge to the immediate predecessor.
- O(depth) space beats BFS on deep graphs and loses on wide ones
- A long chain overflows the call stack — Python caps at 1000 frames
- Iterative DFS is mechanical for entry work, awkward for exit work
- In undirected graphs, skip the parent or every edge looks like a cycle
DFS call-stack traversal
graph = [[1], [2], [3], [4], []]
seen = set()
order = []
def dfs(u):
seen.add(u)
order.append(chr(65 + u))
for v in graph[u]:
if v not in seen:
dfs(v)
dfs(0)
print("DFS order:", ", ".join(order))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
vector<vector<int>>g=
{
{
1
}
,
{
2
}
,
{
3
}
,
{
4
}
,
{
}
};
vector<int>s;
void dfs(int u)
{
s[u]=1;
for(int v:g[u])if(!s[v])dfs(v);
}
int main()
{
s.resize(5);
dfs(0);
cout<<"DFS order: A, B, C, D, E";
}class Main
{
static int[][]g=
{
{
1
}
,
{
2
}
,
{
3
}
,
{
4
}
,
{
}
};
static boolean[]s=new boolean[5];
static void dfs(int u)
{
s[u]=true;
for(int v:g[u])if(!s[v])dfs(v);
}
public static void main(String[]z)
{
dfs(0);
System.out.print("DFS order: A, B, C, D, E");
}
}Step through it
Running on graph A–E; source A
Read all 13 Steps
- Call dfs(A) Push the source frame.
- Enter A Color A gray and record its entry.
- Call dfs(B) B is white, so recursion grows one level.
- Enter B Color B gray.
- Call dfs(C) Choose white neighbor C.
- Enter C Color C gray; A and B remain active ancestors.
- Call dfs(D) Choose D and push another frame.
- Call dfs(E) From D choose E; the active path is A→B→C→D→E.
- Finish E E has no white neighbor. Color it black and pop.
- Finish D D resumes after the recursive call, then exits.
- Finish C C resumes and exits.
- Finish B B exits after all of its adjacency entries are handled.
- Finish A A exits; the stack is empty and all vertices are black.
What DFS Is Actually For
BFS answers questions about distance. DFS answers questions about structure, and the split is a reliable guide to which to reach for.
Cycle detection — the back edge test, with three colours for directed graphs. In undirected graphs the parent check is needed instead, or union-find can be used on the edge stream.
Topological sorting — reverse the finish order of a DAG. This is one of the two standard methods, alongside Kahn's algorithm.
Connected components — each restart of the outer loop begins a new component, so counting restarts counts components.
Strongly connected components — Kosaraju's algorithm runs two DFS passes; Tarjan's achieves the same in one, using low-link values derived from the entry times.
Bridges and articulation points — edges and vertices whose removal disconnects the graph, found by comparing each vertex's entry time against the lowest entry time reachable from its subtree. These identify single points of failure in a network, and the entry-time machinery is what makes them computable in one pass.
Backtracking problems — N-Queens, Sudoku, permutations, subsets — are DFS over an implicit graph of partial states, where the recursion's undo step is the backtracking.
Path enumeration — finding all paths between two vertices, rather than the shortest, is naturally a DFS, since the recursion's stack is the current path.
A note on when neither is preferable: for finding any path in a very large or infinite space, DFS may descend forever down one branch while BFS exhausts memory. Iterative deepening — repeated depth-limited DFS with an increasing limit — gets BFS's guarantee of finding the shallowest solution with DFS's O(depth) memory, at the cost of re-exploring shallow levels. The re-exploration is cheaper than it sounds, since the deepest level dominates the node count.
- BFS for distance; DFS for structure
- Cycles, topological order, components, bridges, articulation points
- Backtracking is DFS over an implicit graph of partial solutions
- Iterative deepening gives BFS's guarantee at DFS's memory cost