Depth-First Search (DFS): Recursive & Iterative Traversal

Depth-First Search (DFS) explores a graph by going as deep as possible along each branch before backtracking. Where BFS fans out level by level, DFS dives down one path until it dead-ends, then retreats and tries the next. It runs in O(V + E) time and underlies cycle detection, topological sort, and connected components.

Recursive DFS

The cleanest DFS rides on the program’s own call stack: visit a vertex, then recurse into each unvisited neighbor.

void dfs(const std::vector<std::vector<int>>& adj, int u,
         std::vector<bool>& visited, std::vector<int>& order) {
    visited[u] = true;
    order.push_back(u);
    for (int v : adj[u])
        if (!visited[v])
            dfs(adj, v, visited, order);
}

void dfs(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> order) {
    visited[u] = true;
    order.add(u);
    for (int v : adj.get(u))
        if (!visited[v])
            dfs(adj, v, visited, order);
}

function dfs(adj, u, visited, order) {
  visited[u] = true;
  order.push(u);
  for (const v of adj[u])
    if (!visited[v])
      dfs(adj, v, visited, order);
}

import sys
sys.setrecursionlimit(1 << 20)  # deep graphs can overflow the default limit

def dfs(adj, u, visited, order):
    visited[u] = True
    order.append(u)
    for v in adj[u]:
        if not visited[v]:
            dfs(adj, v, visited, order)

Pitfall: On a graph with up to ~10⁵ vertices, recursion can overflow the stack. Raise the recursion limit (Python) or use the iterative version below for very deep graphs.

Iterative DFS

Replace the call stack with an explicit stack. To match the recursive visiting order, mark a vertex visited when you pop it (not when you push), and check again on pop because the same vertex may be pushed more than once.

std::vector<int> dfsIterative(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> order;
    std::vector<bool> visited(adj.size(), false);
    std::vector<int> stack{start};
    while (!stack.empty()) {
        int u = stack.back(); stack.pop_back();
        if (visited[u]) continue;
        visited[u] = true;
        order.push_back(u);
        for (int v : adj[u])
            if (!visited[v]) stack.push_back(v);
    }
    return order;
}

List<Integer> dfsIterative(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;
        visited[u] = true;
        order.add(u);
        for (int v : adj.get(u))
            if (!visited[v]) stack.push(v);
    }
    return order;
}

function dfsIterative(adj, start) {
  const order = [];
  const visited = new Array(adj.length).fill(false);
  const stack = [start];
  while (stack.length) {
    const u = stack.pop();
    if (visited[u]) continue;
    visited[u] = true;
    order.push(u);
    for (const v of adj[u])
      if (!visited[v]) stack.push(v);
  }
  return order;
}

def dfs_iterative(adj, start):
    order = []
    visited = [False] * len(adj)
    stack = [start]
    while stack:
        u = stack.pop()
        if visited[u]:
            continue
        visited[u] = True
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                stack.append(v)
    return order

Complexity

Time: O(V + E) — every vertex and edge is touched once.
Space: O(V) for the visited array plus the recursion/explicit stack.

When to use DFS

DFS shines when you need to explore structure rather than find shortest paths: detecting cycles, producing a topological order, finding connected components, or any “explore every path / backtrack” problem. For shortest paths in unweighted graphs, prefer BFS.

Ready to apply traversal? Continue to connected components.