Depth-First Search (DFS)

Overview

Depth-First Search (DFS) explores a graph or tree by going as deep as possible along each branch before backtracking. It is naturally implemented with recursion (the call stack acts as the implicit stack) or with an explicit stack data structure. DFS is essential for problems involving tree traversals, cycle detection, connected components, topological sorting, and path finding.

How It Works

1. 1 Start at the source node and mark it as visited.
2. 2 Explore one unvisited neighbor recursively (or push onto stack).
3. 3 If no unvisited neighbors remain, backtrack to the previous node.
4. 4 Repeat until all reachable nodes are visited.
5. 5 For trees: pre-order (root, left, right), in-order (left, root, right), post-order (left, right, root).

When to Use

• →Tree traversals (pre-order, in-order, post-order)
• →Detecting cycles in a graph
• →Finding connected components
• →Topological sorting (with post-order DFS)
• →Path existence problems ("is there a path from A to B?")
• →Solving puzzles with backtracking (N-Queens, Sudoku)

Common Mistakes

• ⚠Forgetting to mark nodes as visited before recursive calls (causes infinite loops)
• ⚠Not handling disconnected components (need to loop over all nodes)
• ⚠Confusing pre-order/in-order/post-order traversal order
• ⚠Stack overflow from deep recursion on large inputs (use iterative DFS)
• ⚠Modifying the graph while iterating (breaks adjacency lists)

Code Examples

List<Integer> dfs(List<List<Integer>> graph, int node, Set<Integer> visited) {
    visited.add(node);
    List<Integer> result = new ArrayList<>();
    result.add(node);
    for (int neighbor : graph.get(node)) {
        if (!visited.contains(neighbor)) {
            result.addAll(dfs(graph, neighbor, visited));
        }
    }
    return result;
}

void dfs(vector<vector<int>>& graph, int node,
         vector<bool>& visited, vector<int>& result) {
    visited[node] = true;
    result.push_back(node);
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited, result);
        }
    }
}

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    result = [node]
    for neighbor in graph[node]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    return result

function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  const result = [node];
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      result.push(...dfs(graph, neighbor, visited));
    }
  }
  return result;
}

Related Patterns

Practice Problems

Frequently Asked Questions