Depth-First Search (DFS) explores one branch as deeply as possible before backtracking and trying another branch.

It can be implemented with recursion or an explicit stack.

DFS is not only a traversal technique. It is a foundation for cycle detection, connected components, topological sorting, strongly connected components, bridges, articulation points, tree traversals, and backtracking.

Basic recursive DFS

function dfs(graph, start) {
  const visited = new Set();
  const order = [];

  function visit(node) {
    if (visited.has(node)) return;

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

    for (const next of graph[node] ?? []) {
      visit(next);
    }
  }

  visit(start);

  return order;
}

Why visited matters

Graphs may contain cycles.

Without a visited set:

A → B → C → A → B → ...

could recurse forever.

Iterative DFS

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

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

    if (visited.has(current)) continue;

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

    const neighbors = graph[current] ?? [];

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

  return order;
}

DFS vs BFS

| Feature | DFS | BFS | |---|---|---| | Main structure | Stack / recursion | Queue | | Pattern | Deep first | Level first | | Unweighted shortest path | Not guaranteed | Guaranteed | | Backtracking | Natural | Less natural | | Cycle detection | Common | Possible | | Topological sort | Common | Kahn alternative |

Tree traversals

Preorder, inorder, and postorder are all DFS patterns.

Preorder:

Root → Left → Right

Inorder:

Left → Root → Right

Postorder:

Left → Right → Root

Connected components

Run DFS from every unvisited vertex.

Each new DFS call discovers one component.

Reachability

DFS naturally answers:

Can target be reached from start?

by recursively exploring all reachable neighbors.

Cycle detection in undirected graphs

In undirected graphs, seeing a visited neighbor is only a cycle if that neighbor is not the current node's parent.

function hasCycleUndirected(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        if (dfs(next, node)) return true;
      } else if (next !== parent) {
        return true;
      }
    }

    return false;
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node) && dfs(node, null)) {
      return true;
    }
  }

  return false;
}

Cycle detection in directed graphs

Directed graphs need information about the active recursion path.

A common three-state model is:

0 = unvisited
1 = visiting
2 = finished

An edge to a visiting vertex is a back edge and proves a cycle.

function hasCycleDirected(graph) {
  const state = new Map();

  function dfs(node) {
    state.set(node, 1);

    for (const next of graph[node] ?? []) {
      const nextState = state.get(next) ?? 0;

      if (nextState === 1) return true;

      if (nextState === 0 && dfs(next)) {
        return true;
      }
    }

    state.set(node, 2);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if ((state.get(node) ?? 0) === 0) {
      if (dfs(node)) return true;
    }
  }

  return false;
}

Topological sort

DFS can create a topological ordering by adding each vertex after all outgoing dependencies are processed.

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

  function dfs(node) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        dfs(next);
      }
    }

    order.push(node);
  }

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

  return order.reverse();
}

A production implementation should also detect cycles because topological ordering requires a DAG.

DFS and backtracking

Backtracking is often DFS over a state-space tree with an additional choose/undo pattern.

choose
recurse
undo

Examples include permutations, combinations, Sudoku, N-Queens, and Hamiltonian search.

Maze and grid search

DFS works naturally for reachability, flood fill, connected regions, and island counting.

For shortest paths in an unweighted maze, BFS is normally a better choice.

Number of Islands

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  let count = 0;

  function dfs(r, c) {
    if (
      r < 0 ||
      r >= rows ||
      c < 0 ||
      c >= cols ||
      grid[r][c] !== "1"
    ) {
      return;
    }

    grid[r][c] = "0";

    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

Real-world applications

• recursive file-system traversal,
• DOM and AST traversal,
• dependency analysis,
• circular-dependency detection,
• build systems,
• graph components,
• network topology,
• maze and puzzle search,
• source-code analysis.

Discovery and finish times

DFS naturally has entry and exit events for each vertex.

These timestamps are fundamental in more advanced algorithms such as topological sort, SCC algorithms, bridges, and articulation points.

Recursive vs iterative DFS

Recursive DFS is concise and natural.

However, very deep graphs can overflow the language call stack.

Iterative DFS is safer for extremely deep graphs and gives explicit control over traversal state.

Complexity

With an adjacency list:

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

With an adjacency matrix, neighbor scanning can lead to:

O(V²)

time.

Common mistakes

• forgetting visited,
• assuming DFS gives shortest paths,
• missing disconnected components,
• using only visited for directed cycle detection,
• causing stack overflow with very deep recursion,
• confusing permanent visited state with temporary backtracking state.

TypeScript

type Graph = Record<string, string[]>;

function dfs(
  graph: Graph,
  start: string
): string[] {
  const visited = new Set<string>();
  const order: string[] = [];

  function visit(node: string): void {
    if (visited.has(node)) return;

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

    for (const next of graph[node] ?? []) {
      visit(next);
    }
  }

  visit(start);

  return order;
}

When should you use DFS?

Use DFS for:

• deep traversal,
• reachability,
• connected components,
• cycle detection,
• topological ordering,
• dependency graphs,
• backtracking,
• tree traversals,
• SCC, bridges, and articulation-point algorithms.

When is DFS not the right tool?

Use BFS for unweighted shortest paths.

Use Dijkstra or Bellman-Ford for weighted shortest-path problems depending on edge properties.

Use iterative DFS when recursion depth may become unsafe.

Summary

DFS follows one branch deeply, backtracks at a dead end, and continues through the next branch.

Its standard adjacency-list complexity is:

O(V + E)

DFS is one of the most reusable patterns in graph algorithms because many advanced algorithms are built on top of its recursion tree, discovery order, finish order, and back edges.