Graph AlgosAlgorithmaka DFS, depth-first traversal

Depth-First Search (DFS)

Explore a graph by following one path as deep as possible before backtracking, using recursion or an explicit stack.

▶ VisualizePattern: Depth-First SearchPractice (6)
Progress

Overview

DFS starts at a source, moves to an unvisited neighbour, and keeps going deeper until it hits a dead end; then it backtracks to the most recent node that still has an unexplored neighbour. The natural implementation is recursion; the call stack is the Stack of the path currently being explored.

Unlike Breadth-First Search (BFS), DFS does not find shortest paths, but it exposes structure that BFS cannot: discovery and finishing times, tree/back/forward/cross edge classification, and a natural post-order. That structure underpins Topological Sort, Cycle Detection, Tarjan's SCC Algorithm, Bridges and Articulation Points.

traversalstackrecursionbacktrackingO(V + E)

Intuition

A mental model before the formal terms.

Walking a maze with a ball of string: at each junction you take an untried corridor, unrolling string behind you. At a dead end you rewind the string to the previous junction and try another corridor. The string is the recursion stack; the chalk marks on visited junctions are the visited set. You eventually see every reachable room, but the first route you find to the exit is rarely the shortest.

How it works

  1. Mark u visited and record its discovery (pre-order) time.
  2. For each neighbour v of u: if unvisited, set parent[v] = u and recurse into v. If already visited and still on the stack (in a directed graph), u → v is a back edge — a cycle.
  3. After all neighbours are processed, record the finish (post-order) time of u. Reverse finishing order is a topological order on a DAG.
  4. Iterative version: push s; pop u; if unvisited, mark it and push all its unvisited neighbours. To reproduce recursive pre-order exactly, push neighbours in reverse order; to get post-order, keep an iterator index per stack frame instead of popping nodes.

Why it works

Every node is marked before recursion into it and never unmarked, so each node is entered once and each adjacency list scanned once: O(V + E).

The white-path theorem: v becomes a descendant of u in the DFS tree iff at the moment u is discovered there is a path from u to v through undiscovered nodes. This is what makes finishing times meaningful for topological sorting and SCCs.

Parenthesis structure: for any two nodes the intervals [discover, finish] are either nested or disjoint, never partially overlapping — exactly what a stack produces.

Recognition

How to tell a problem wants this.

  • You need to know whether a path exists, not how long it is (reachability, flood fill, count components).
  • The problem talks about cycles, dependencies, ordering, "can all courses be finished".
  • You must enumerate all paths or all configurations — DFS with undo is Recursion & Backtracking/backtracking.
  • Tree problems where each node needs information from its subtree (post-order): heights, diameters, subtree sums.
“connected groups” → Depth-First Search

Interactive visualization

Play, step, change the input. ← → and space work too.

ABCDEFGH
Stack (top → bottom)
A
Discovery order
empty
1/18Start DFS from A. The explicit stack replaces the recursion: the node on top is explored next, so we dive deep before going wide.
Current nodeOn the stackVisited (label = discovery order)DFS tree edge
PseudocodeLearn Depth-First Search (DFS) →
1stack = [source]; visited = {}; order = []
2while stack not empty:
3  u = stack.pop()
4  if u in visited: continue
5  visited.add(u); order.append(u)
6  for v in reversed(neighbors(u)):
7    if v not in visited: stack.push(v)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1def dfs(u):
2  visited.add(u); pre.append(u)
3  for v in adj[u]:
4    if v not in visited:
5      parent[v] = u; dfs(v)
6  post.append(u)
7for s in nodes: if s not in visited: dfs(s)

Implementations

1import sys
2 
3 
4def dfs(adj: list[list[int]], s: int) -> tuple[list[int], list[int], list[int]]:
5    """Recursive DFS. Returns (pre-order, post-order, parent)."""
61 · State
7    sys.setrecursionlimit(max(10_000, len(adj) + 100))
8    n = len(adj)
9    visited = [False] * n
10    parent = [-1] * n
11    pre: list[int] = []
12    post: list[int] = []
13 
142 · Recursive visit
15    def run(u: int) -> None:
16        visited[u] = True
17        pre.append(u)
183 · Explore neighbours
19        for v in adj[u]:
20            if not visited[v]:
21                parent[v] = u
22                run(v)
234 · Post-order
24        post.append(u)
25 
26    run(s)
27    return pre, post, parent
28 
29 
305 · Iterative pre-order (same order as recursive, no stack-depth limit)
31def dfs_iterative(adj: list[list[int]], s: int) -> list[int]:
32    seen = [False] * len(adj)
33    order: list[int] = []
34    stack = [s]
35    while stack:
36        u = stack.pop()
37        if seen[u]:
38            continue
39        seen[u] = True
40        order.append(u)
41        for v in reversed(adj[u]):     # reversed so the first neighbour is popped first
42            if not seen[v]:
43                stack.append(v)
44    return order
Walkthrough
  1. sys.setrecursionlimit raises the default limit of 1000 so a path graph of a few thousand nodes does not crash.
  2. run is a nested function that closes over the outer lists; it needs no nonlocal because it only mutates, never rebinds.
  3. Pre-order appends before the loop, post-order after — the same shape as the C++ and JS versions.
  4. dfs_iterative uses reversed(adj[u]) so neighbours are popped in original order; nodes already seen are skipped at pop time.
Complexity (this implementation)
time O(V + E) · space O(V)

Python frames are heavy (~500 bytes+) and the interpreter C stack can segfault around 10^5 frames even after raising the limit; prefer dfs_iterative beyond a few thousand nodes.

Language notes
  • sys.setrecursionlimit only changes the interpreter guard, not the OS stack; use threading.stack_size or iteration for really deep graphs.
  • A list is Python's native stack: append / pop() are amortised O(1).
  • reversed() returns an iterator, so no copy of the neighbour list is made.
Common mistakes in this language
  • Forgetting sys.setrecursionlimit and getting RecursionError on a 1000-node chain.
  • Rebinding a closed-over list (pre = pre + [u]) inside the nested function, which needs nonlocal and copies.
  • Marking seen at push time in the iterative version.
Language differences that matter here
  • Recursion limits differ sharply: Python defaults to 1000 frames (raise with sys.setrecursionlimit), JS/TS engines allow ~10k, C++ depends on the OS stack (~10^5–10^6). The iterative version is the portable safe choice.
  • C++ needs a struct or reference parameters to share state; JS/TS/Python use closures over outer variables.
  • Stack primitive: C++ std::stack (top/pop are separate), JS/TS arrays (push/pop), Python lists (append/pop).

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Recursion depth can reach V on a path graph — Python's default limit of 1000 and typical JS engines (~10k frames) overflow; use the iterative form for n ≥ 10^4.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Reachability, flood fill, counting Connected Components — any "does a path exist" question.
  • Anything needing post-order: DFS Topological Sort, subtree aggregation, Tarjan's SCC Algorithm, Bridges.
  • Cycle detection in directed graphs via the three-colour (white/grey/black) scheme.
  • Enumerating all paths or combinations with backtracking, where BFS would have to store every partial path.
Avoid it when
  • Shortest path by edge count — DFS finds *a* path, not the shortest; use Breadth-First Search (BFS).
  • Extremely deep graphs with recursion (long chains, big grids): stack overflow. Switch to the explicit-stack version.
  • Nearest-goal search in a huge implicit space: DFS may wander down an infinite or enormous branch; BFS or iterative deepening is safer.

Alternatives

Breadth-First Search (BFS)Recursion & BacktrackingUnion-Find (Disjoint Set Union)
Compare: BFS vs DFS

Common mistakes

  • Iterative DFS that marks visited at push time produces a different (and sometimes wrong for post-order) order than recursive DFS — mark at pop time and skip already-visited pops.
  • In an undirected graph, treating the edge back to the parent as a cycle. Skip v == parent[u] (or, with multi-edges, skip by edge id).
  • Using a plain visited flag for directed cycle detection — you need "on the current stack" (grey) versus "finished" (black).
  • Forgetting sys.setrecursionlimit in Python, or relying on recursion for a 1000×1000 grid.
  • Mutating the shared adjacency list during traversal.

Interview patterns

  • Grid flood fill: number of islands, max area of island, surrounded regions.
  • Directed cycle detection with colours: course schedule, detect deadlock.
  • Post-order aggregation on trees: diameter, max path sum, subtree sizes (Tree DP).
  • Backtracking enumeration: subsets, permutations, word search — DFS over an implicit state tree with undo.
  • Clone graph: DFS with a hash map from original node to its copy.
Interview questions on this
Mock interviews

Example problems

Number of IslandsmediumClone GraphmediumReconstruct ItineraryhardCourse SchedulemediumBinary Tree Maximum Path SumhardWord Searchmedium