Depth-first search
easyRecursive or iterative, with the call stack made visible either way. Turn on component restarting and the same traversal becomes a connected-components scan.
O(V + E)Space O(V) stack depthSaved in this browser - no sign-up, nothing sent anywhere.
How depth-first search works
Depth-first search commits to one branch until it dead-ends, then backtracks one step and tries the next. Structurally it is BFS with the queue replaced by a stack - that single swap changes the order from nearest-first to deepest-first, and every behavioural difference between the two follows from it.
This module shows both forms. The recursive version uses the call stack itself: dfs(u) marks u, then recurses into each unseen neighbour. The iterative version makes that stack explicit, popping a node, skipping it if already seen - one node can be pushed twice - and pushing unseen neighbours in reverse so the visit order matches.
DFS's real payoff is the finishing order. A node finishes only after everything reachable below it has finished, and that timestamp is what topological sorting, cycle detection and strongly connected components are built from - BFS never produces it. Turn on component restarting here and the same traversal counts connected components in one O(V + E) pass.
Step by step
- Call dfs(A). A is marked and its frame goes on the call stack, where it stays until every branch below it is exhausted.
- A's first neighbour is B - recurse straight in without looking at D. Depth always wins over breadth.
- The dive continues: B to C, C to F, F to E. Each frame stacks on top; the path is now five deep.
- From E, neighbour B is already seen - skip - but D is new. D leads to G, and G to H.
- H's neighbours E and G are both seen, so H finishes first and its frame pops. The recursion unwinds through G and D.
- Back at A, neighbour D is long since visited. A finishes last, with visit order A, B, C, F, E, D, G, H.
Complexity
| Worst case time | O(V + E) |
|---|---|
| Space | O(V) stack depth |
Memory is proportional to the depth of the current path, not the width.
Reference implementation
Python
def dfs(adj, u, seen=None, order=None):
seen = set() if seen is None else seen
order = [] if order is None else order
seen.add(u)
order.append(u)
for v in adj[u]:
if v not in seen:
dfs(adj, v, seen, order)
return order
def dfs_iterative(adj, start):
"""Same traversal, explicit stack - no recursion depth limit."""
seen, order, stack = set(), [], [start]
while stack:
u = stack.pop()
if u in seen:
continue
seen.add(u)
order.append(u)
for v in reversed(adj[u]): # reversed keeps the same order
if v not in seen:
stack.append(v)
return orderJavaScript
function dfs(adj, u, seen = new Set(), order = []) {
seen.add(u);
order.push(u);
for (const v of adj.get(u) ?? []) {
if (!seen.has(v)) dfs(adj, v, seen, order);
}
return order;
}
function dfsIterative(adj, start) {
const seen = new Set(), order = [], stack = [start];
while (stack.length) {
const u = stack.pop();
if (seen.has(u)) continue;
seen.add(u);
order.push(u);
for (const v of [...(adj.get(u) ?? [])].reverse()) {
if (!seen.has(v)) stack.push(v);
}
}
return order;
}Worth noticing
Stack instead of queue - that is the only difference from BFS
Both algorithms discover the same nodes and both are O(V+E). Swapping the container changes the order from 'nearest first' to 'deepest first', and every behavioural difference between them follows from that one choice.
DFS does not find shortest paths
The path it reaches a node by is whatever the recursion happened to take first - often long and winding. If you need distances, use BFS.
Memory is proportional to depth
The stack holds one entry per level of the current path. On a long chain that means O(V) frames and a real risk of stack overflow - which is why the iterative version exists.
The finishing order is what makes DFS powerful
Topological sort, strongly connected components, bridges and articulation points all depend on *when a node finishes*, not when it starts. That information is free in DFS and unavailable in BFS.
Common pitfalls
- Recursing on deep graphs. A path graph of 100,000 nodes means 100,000 stack frames - a stack overflow in most languages. That is exactly why the iterative version exists.
- Forgetting the seen check on pop in iterative DFS. This variant pushes a node once per discovering neighbour, so without the check nodes get visited repeatedly.
- Using DFS for shortest paths. The route it takes is whatever branch came first - on the default graph it reaches E in four hops when the shortest is two.
- Pushing neighbours in forward order and wondering why the iterative order differs from the recursive one. The stack reverses; push them reversed to match, as the code here does.
- Stopping after one component. Any node unreachable from the start is simply never seen - wrap the traversal in a loop over unvisited nodes.
Where it is used
- Cycle detection and topological sorting in dependency graphs - the finishing order is the topological order, reversed.
- Connected components, flood fill and island counting - number of islands is DFS restarted per unvisited cell.
- Maze solving and backtracking searches, where one deep probe with undo is the whole strategy.
- Compilers and static analysis: strongly connected components via Tarjan's algorithm are DFS finish times put to work.
Frequently asked questions
What is the time and space complexity of DFS?
O(V + E) time, the same as BFS - every vertex and edge is touched a constant number of times. Space is O(V) stack depth in the worst case, but it is proportional to the depth of the current path, the opposite trade-off from BFS's width.
Should I write DFS recursively or iteratively?
They visit the same nodes in the same O(V + E) time. Recursive is shorter and gives finishing order naturally; iterative trades that for immunity to stack overflow, which matters once depth reaches the tens of thousands. Interviews accept either - production code on unknown inputs should prefer iterative.
Can DFS find the shortest path?
Not reliably. DFS reaches each node by the first route the recursion stumbled into, which can be arbitrarily longer than optimal. Use BFS on unweighted graphs and Dijkstra on weighted ones; use DFS for reachability, cycles, ordering and exhaustive exploration.
How do I find connected components with DFS?
Loop over every vertex; whenever one is still unvisited, increment a counter and run DFS from it, labelling everything reached. The toggle in this visualizer does exactly that - the whole scan is still one O(V + E) pass because each vertex is visited once.