Skip to content

Depth-First Search

First PublishedByAtif Alam

Difficulty: Medium. ROI: High.

Other common names: DFS, depth-first traversal.

When to use: Use when you need to explore all paths, detect cycles, do topological sort, or traverse a graph/tree and process on the way down or back up (pre/in/post order).

Idea: Go deep from a node (recurse or push neighbors onto a stack), then backtrack. Mark visited nodes to avoid revisiting. Can be implemented recursively or with an explicit stack.

Time / space: O(V + E) for a graph; O(n) for a tree. Space O(h) for recursion stack (height of tree or graph depth).

Example #1 — DFS Traversal

Section titled “Example #1 — DFS Traversal”

Traverse a graph by going as deep as possible from each node, then backtracking. Use a shared visited set and recurse into each unvisited neighbor.

Sample input and output

graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}
dfs(graph, 1)  # traverses all reachable nodes; visit order 1 → 2 → 4 → 3 if you append in "process node"
  • Sample input: graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}, start node 1.
  • Sample output: With the code above, every node is visited once. If you add e.g. order.append(node) in the “process node” place, the visit order is [1, 2, 4, 3] (DFS goes 1 → 2 → 4, then backtracks and visits 3 from 1).

Code (with inline comments)

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()  # shared across recursive calls so we don't revisit
    visited.add(node)


    # process node here
    for neighbor in graph[node]:
        if neighbor not in visited:  # only recurse into unvisited nodes
            dfs(graph, neighbor, visited)

Line-by-line:

  • def dfs(graph, node, visited=None): — We define a function that takes the graph (e.g. a dict mapping each node to a list of its neighbors), the current node we’re at, and an optional visited container. Using visited=None as the default lets the caller call dfs(graph, start) without passing visited; we create it inside the function on the first call.
  • if visited is None: — This is true only on the very first call (when the caller didn’t pass visited). On recursive calls we always pass the same visited object so every call shares it.
  • visited = set() — We create a set: an unordered collection that stores unique values and lets us check “is this value in here?” very quickly. We use it to remember which nodes we’ve already visited so we don’t process the same node twice (and don’t get stuck in cycles).
  • visited.add(node) — We mark the current node as visited by adding it to the set. From now on we’ll skip this node if we see it again.
  • # process node here — This is where you’d do whatever you need for each node (e.g. print it, collect it, check a condition). DFS guarantees we visit each node once (for a connected graph when we pass the same visited).
  • for neighbor in graph[node]: — We loop over every neighbor of the current node. graph[node] is the list (or iterable) of nodes that node is connected to (e.g. for an adjacency list like {1: [2, 3], 2: [1], 3: [1]}).
  • if neighbor not in visited: — We only recurse into neighbors we haven’t visited yet. This avoids infinite loops on cycles and avoids revisiting nodes.
  • dfs(graph, neighbor, visited) — We call DFS recursively on the neighbor, passing the same graph and the same visited set so that the whole traversal shares one set of visited nodes. The recursion “goes deep” (follows one path as far as possible) before trying other neighbors.

Execution trace (numbered list)

For graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}, start 1:

  1. Step 1: dfs(1), visited = {1}. Recurse into neighbor 2.
  2. Step 2: dfs(2), visited = {1, 2}. Recurse into neighbor 4 (1 already visited).
  3. Step 3: dfs(4), visited = {1, 2, 4}. Neighbor 2 already visited. Return.
  4. Step 4: Back in dfs(2). No more neighbors. Return.
  5. Step 5: Back in dfs(1). Recurse into neighbor 3.
  6. Step 6: dfs(3), visited = {1, 2, 4, 3}. Neighbor 1 already visited. Return.
  7. Step 7: Back in dfs(1). No more neighbors. Done. Visit order: 1 → 2 → 4 → 3.

Execution trace (code with step comments)

# dfs(1) → add 1, recurse to 2
#   dfs(2) → add 2, recurse to 4
#     dfs(4) → add 4, 2 in visited → return
#   back in dfs(2) → return
# back in dfs(1) → recurse to 3
#   dfs(3) → add 3, 1 in visited → return
# back in dfs(1) → done. order = [1, 2, 4, 3]

Execution trace (ASCII diagram)

Graph and DFS visit order (go deep first, then backtrack):

Graph:  1 --- 2 --- 4
        |     |
        +-- 3-+


Visit order:  1 → 2 → 4 (backtrack) → 3
              [1]  [2]  [4]            [3]