Depth-First Search (DFS) Algorithm

What Is Depth-First Search (DFS)?

Depth-First Search (DFS) is a graph traversal algorithm that explores a path as deeply as possible before returning to explore another path. Instead of visiting all nearby vertices first, DFS follows one neighbor, then continues through that neighbor's neighbors until it reaches a point where it cannot continue.

DFS can be implemented using recursion or an explicit stack. Both approaches follow the same depth-first idea.

How DFS Traverses a Graph

Consider the following graph:

        A
       / \
      B   C
     / \
    D   E

If DFS starts at A and neighbors are processed in the order shown, one possible traversal is:

A → B → D → E → C

DFS first moves from A to B, then goes deeper to D. After D has no unvisited neighbors, DFS backtracks to B and explores E. It eventually returns to A and explores C.

DFS and Backtracking

Backtracking is one of the most important ideas behind DFS. When the current vertex has no unvisited neighbor, the algorithm returns to the previous vertex and checks whether another path is available.

A
|
B
|
D

D has no unvisited neighbor
        ↓
Backtrack to B
        ↓
Explore another neighbor of B

This depth-and-backtrack behavior also appears in maze solving, tree traversal, dependency analysis, connected-component algorithms, and many recursive problem-solving techniques.

DFS Using Recursion

Recursive DFS uses the JavaScript call stack as its implicit stack. When a vertex is visited, the function recursively explores each unvisited neighbor.

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) {
    return;
  }

  visited.add(node);
  console.log(node);

  for (const neighbor of graph.get(node) || []) {
    dfs(graph, neighbor, visited);
  }
}

const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A']],
  ['D', ['B']],
  ['E', ['B']]
]);

dfs(graph, 'A');

// A
// B
// D
// E
// C

The visited set prevents DFS from repeatedly traversing vertices when the graph contains cycles.

DFS Using an Explicit Stack

DFS does not require recursion. An explicit stack can be used to make the traversal iterative. This approach is useful when you want direct control over the stack or want to avoid very deep recursive call chains.

function dfsIterative(graph, start) {
  const stack = [start];
  const visited = new Set();
  const result = [];

  while (stack.length > 0) {
    const current = stack.pop();

    if (visited.has(current)) {
      continue;
    }

    visited.add(current);
    result.push(current);

    const neighbors = graph.get(current) || [];

    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }

  return result;
}

const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A']],
  ['D', ['B']],
  ['E', ['B']]
]);

console.log(dfsIterative(graph, 'A'));
// ['A', 'B', 'D', 'E', 'C']

The neighbors are pushed in reverse order so that the stack processes them in the same left-to-right order as the recursive example. The exact traversal order is not universal; it depends on how neighbors are stored and processed.

Why Does DFS Need a Visited Set?

Graphs can contain cycles, meaning a path can eventually lead back to a vertex that has already been visited.

A → B
↑   ↓
└── C

Without a visited structure, DFS could keep following the cycle: A → B → C → A → B → C.

The visited set records vertices that have already been discovered, allowing DFS to stop revisiting them.

DFS with an Adjacency List

An adjacency list is one of the most convenient graph representations for DFS because the algorithm can directly iterate through the neighbors of the current vertex.

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'E'],
  D: ['B'],
  E: ['B', 'C']
};

function dfs(graph, node, visited = new Set(), result = []) {
  if (visited.has(node)) {
    return result;
  }

  visited.add(node);
  result.push(node);

  for (const neighbor of graph[node] || []) {
    dfs(graph, neighbor, visited, result);
  }

  return result;
}

console.log(dfs(graph, 'A'));
// ['A', 'B', 'D', 'E', 'C']

DFS with an Adjacency Matrix

DFS can also work with an adjacency matrix. Instead of iterating through a neighbor list, the algorithm checks each possible vertex to determine whether an edge exists.

const matrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 0],
  [0, 1, 0, 0]
];

function dfsMatrix(matrix, start, visited = new Set(), result = []) {
  visited.add(start);
  result.push(start);

  for (let neighbor = 0; neighbor < matrix.length; neighbor++) {
    if (matrix[start][neighbor] === 1 && !visited.has(neighbor)) {
      dfsMatrix(matrix, neighbor, visited, result);
    }
  }

  return result;
}

console.log(dfsMatrix(matrix, 0));
// [0, 1, 3, 2]

With an adjacency matrix, checking all possible neighbors requires O(V) work for each processed vertex. This is one reason adjacency lists are often preferred for sparse graphs.

DFS for Searching a Target

DFS can stop as soon as a target vertex is found. This is useful when the goal is simply to determine whether a vertex is reachable from another vertex.

function dfsSearch(graph, current, target, visited = new Set()) {
  if (current === target) {
    return true;
  }

  visited.add(current);

  for (const neighbor of graph.get(current) || []) {
    if (!visited.has(neighbor)) {
      if (dfsSearch(graph, neighbor, target, visited)) {
        return true;
      }
    }
  }

  return false;
}

const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['D']],
  ['C', ['E']],
  ['D', []],
  ['E', []]
]);

console.log(dfsSearch(graph, 'A', 'E'));
// true

console.log(dfsSearch(graph, 'A', 'X'));
// false

DFS for Finding a Path

DFS can record the previous vertex while exploring the graph. If the target is found, the stored parent information can be used to reconstruct a path.

function dfsPath(graph, start, target) {
  const visited = new Set();
  const previous = new Map();

  function search(current) {
    if (visited.has(current)) {
      return false;
    }

    visited.add(current);

    if (current === target) {
      return true;
    }

    for (const neighbor of graph.get(current) || []) {
      if (!visited.has(neighbor)) {
        previous.set(neighbor, current);

        if (search(neighbor)) {
          return true;
        }
      }
    }

    return false;
  }

  if (!search(start)) {
    return [];
  }

  const path = [];
  let current = target;

  while (current !== undefined) {
    path.push(current);
    current = previous.get(current);
  }

  return path.reverse();
}

const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['D']],
  ['C', ['E']],
  ['D', ['F']],
  ['E', ['F']],
  ['F', []]
]);

console.log(dfsPath(graph, 'A', 'F'));
// ['A', 'B', 'D', 'F']

DFS can find a path, but the path it finds is not necessarily the shortest path in an unweighted graph. If the problem specifically asks for the minimum number of edges or minimum moves, BFS is generally the appropriate traversal.

DFS for Connected Components

DFS can be used to find connected components in an undirected graph. Start DFS from every vertex that has not yet been visited. Each DFS traversal discovers one complete component.

function countComponents(graph) {
  const visited = new Set();
  let count = 0;

  function dfs(node) {
    if (visited.has(node)) {
      return;
    }

    visited.add(node);

    for (const neighbor of graph.get(node) || []) {
      dfs(neighbor);
    }
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      count++;
      dfs(node);
    }
  }

  return count;
}

const graph = new Map([
  ['A', ['B']],
  ['B', ['A']],
  ['C', ['D']],
  ['D', ['C']],
  ['E', []]
]);

console.log(countComponents(graph));
// 3

DFS for Cycle Detection

DFS is commonly used to detect cycles. The exact technique depends on whether the graph is directed or undirected.

In a directed graph, a common approach tracks vertices currently present in the recursion path. Encountering a vertex that is already in that active path indicates a back edge and therefore a cycle.

function hasCycle(graph) {
  const visited = new Set();
  const visiting = new Set();

  function dfs(node) {
    if (visiting.has(node)) {
      return true;
    }

    if (visited.has(node)) {
      return false;
    }

    visiting.add(node);

    for (const neighbor of graph.get(node) || []) {
      if (dfs(neighbor)) {
        return true;
      }
    }

    visiting.delete(node);
    visited.add(node);

    return false;
  }

  for (const node of graph.keys()) {
    if (dfs(node)) {
      return true;
    }
  }

  return false;
}

const graph = new Map([
  ['A', ['B']],
  ['B', ['C']],
  ['C', ['A']]
]);

console.log(hasCycle(graph));
// true

DFS in Trees

DFS is also fundamental to tree traversal. A binary tree can be explored using preorder, inorder, or postorder traversal.

        1
       / \
      2   3
     / \
    4   5

Preorder:  1 → 2 → 4 → 5 → 3
Inorder:   4 → 2 → 5 → 1 → 3
Postorder: 4 → 5 → 2 → 3 → 1

These traversals are DFS patterns because the algorithm explores a branch before moving back to another branch.

DFS Preorder Traversal

In preorder traversal, the current node is processed before its children.

function preorder(node, result = []) {
  if (node === null) {
    return result;
  }

  result.push(node.value);
  preorder(node.left, result);
  preorder(node.right, result);

  return result;
}

DFS Postorder Traversal

In postorder traversal, child nodes are processed before the current node. This pattern is useful when a parent depends on work being completed for its children first.

function postorder(node, result = []) {
  if (node === null) {
    return result;
  }

  postorder(node.left, result);
  postorder(node.right, result);
  result.push(node.value);

  return result;
}

DFS and Topological Sorting

DFS can be used to produce a topological ordering of a directed acyclic graph (DAG). A common approach is to perform DFS and add a vertex to a result stack after all of its outgoing neighbors have been processed.

function topologicalSort(graph) {
  const visited = new Set();
  const result = [];

  function dfs(node) {
    if (visited.has(node)) {
      return;
    }

    visited.add(node);

    for (const neighbor of graph.get(node) || []) {
      dfs(neighbor);
    }

    result.push(node);
  }

  for (const node of graph.keys()) {
    dfs(node);
  }

  return result.reverse();
}

const graph = new Map([
  ['Learn', ['Practice']],
  ['Practice', ['Build']],
  ['Build', []]
]);

console.log(topologicalSort(graph));
// ['Learn', 'Practice', 'Build']

A production implementation of topological sorting should also detect cycles because a directed graph containing a cycle does not have a valid topological ordering.

DFS Time and Space Complexity

With an adjacency list, DFS visits each reachable vertex and examines each relevant edge.

• Time complexity: O(V + E)
• Space complexity: O(V)

Here, V is the number of vertices and E is the number of edges. The O(V) space can come from the visited set and the DFS stack, whether that stack is explicit or represented by the recursive call stack.

With an adjacency matrix, DFS may spend O(V) time checking possible neighbors for every vertex, resulting in O(V²) traversal time.

BFS vs DFS

BFS and DFS both traverse graphs, but their exploration strategies are different.

When Should You Use DFS?

DFS is useful when the problem benefits from exploring an entire branch before moving to another branch.

• Traversing trees and hierarchical structures.
• Detecting cycles in graphs.
• Finding connected components.
• Checking whether a path exists between vertices.
• Topological sorting of directed acyclic graphs.
• Backtracking and state-space exploration.
• Maze and grid exploration.
• Dependency and prerequisite analysis.
• Exploring nested or hierarchical data.

DFS in Grid Problems

A grid can be modeled as a graph where each walkable cell is a vertex and neighboring cells are connected. DFS can explore an entire region of connected cells.

This makes DFS useful for problems such as counting islands, exploring rooms, identifying connected regions, and checking whether cells are reachable.

const grid = [
  ['1', '1', '0'],
  ['1', '0', '0'],
  ['0', '0', '1']
];

function dfs(grid, row, col) {
  if (
    row < 0 ||
    row >= grid.length ||
    col < 0 ||
    col >= grid[0].length ||
    grid[row][col] !== '1'
  ) {
    return;
  }

  grid[row][col] = '0';

  dfs(grid, row + 1, col);
  dfs(grid, row - 1, col);
  dfs(grid, row, col + 1);
  dfs(grid, row, col - 1);
}

dfs(grid, 0, 0);

console.log(grid);
// Connected cells from the starting position have been explored.

Recursive DFS vs Iterative DFS

Both implementations perform depth-first traversal, but they manage traversal state differently.

Common DFS Mistakes

1. Forgetting to Track Visited Vertices

A graph can contain cycles, so DFS needs a way to identify vertices that have already been explored.

2. Assuming DFS Finds the Shortest Path

DFS may find a valid path without finding the path with the fewest edges. Use BFS when the problem asks for the shortest path in an unweighted graph.

3. Ignoring Neighbor Order

DFS traversal order depends on the order in which neighbors are processed. More than one traversal can therefore be valid for the same graph.

4. Using Deep Recursion Without Considering Stack Limits

Very deep graphs can produce a large recursive call stack. An iterative implementation with an explicit stack can be preferable for such cases.

5. Confusing Graph DFS with Tree DFS

Tree traversal often relies on the tree structure itself, while a general graph may contain cycles and multiple paths to the same vertex. Graph DFS therefore normally requires explicit visited tracking.

DFS Interview Pattern

DFS is often a useful first consideration when an interview problem involves exploring all possibilities, connected regions, recursive relationships, or graph structure.

• Ask whether the problem can be modeled as a graph or tree.
• Identify the starting vertex or state.
• Determine how neighboring states are generated.
• Decide whether visited tracking is required.
• Choose recursion or an explicit stack.
• Return or record information while exploring and backtracking.

Words such as explore, connected, reachability, all possible paths, cycle, and dependencies can be useful clues that DFS may fit the problem.

Key Takeaways

• DFS explores a graph deeply before backtracking.
• DFS can be implemented recursively or with an explicit stack.
• A visited set is important when traversing general graphs with cycles.
• DFS works naturally with tree and hierarchical structures.
• DFS is useful for connected components, cycle detection, path existence, and topological sorting.
• DFS does not guarantee the shortest path in an unweighted graph.
• With an adjacency list, DFS runs in O(V + E) time.
• The exact DFS traversal order depends on neighbor ordering.