Depth-First Search

Why This Matters

Some problems require exploring every possible path to its end before trying alternatives. Checking if a maze has a solution, detecting cycles in dependencies, finding all possible routes, and solving puzzles by trial and error all follow this pattern. Depth-first search (DFS) goes as deep as possible down one path before backtracking and trying the next.

Where BFS explores level by level (wide before deep), DFS explores branch by branch (deep before wide). DFS naturally maps to recursion — each recursive call explores one neighbor's entire subtree before returning. DFS is the backbone of topological sorting, cycle detection, connected component analysis, and many backtracking algorithms. If BFS is a careful sweep of the room, DFS is following one hallway to the very end before coming back.

Define Terms

Visual Model

Code Example

// RECURSIVE DFS
function dfsRecursive(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);

  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited);
    }
  }
}

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

console.log("Recursive DFS:");
dfsRecursive(graph, "A"); // A, B, D, E, F, C

// ITERATIVE DFS (using explicit stack)
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const node = stack.pop(); // LIFO — last in, first out
    if (visited.has(node)) continue;

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

    // Add neighbors in reverse for consistent order
    for (let i = graph[node].length - 1; i >= 0; i--) {
      if (!visited.has(graph[node][i])) {
        stack.push(graph[node][i]);
      }
    }
  }

  return order;
}

console.log("Iterative DFS:", dfsIterative(graph, "A"));

// CYCLE DETECTION in directed graph
function hasCycle(graph) {
  const visited = new Set();
  const inStack = new Set(); // currently in recursion stack

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

    for (const neighbor of (graph[node] || [])) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) return true;
      } else if (inStack.has(neighbor)) {
        return true; // back edge = cycle!
      }
    }

    inStack.delete(node);
    return false;
  }

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

const dag = { A: ["B", "C"], B: ["D"], C: ["D"], D: [] };
const cyclic = { A: ["B"], B: ["C"], C: ["A"] };
console.log("DAG has cycle?", hasCycle(dag));       // false
console.log("Cyclic has cycle?", hasCycle(cyclic)); // true

Interactive Experiment

Try these exercises:

• Trace DFS on the example graph starting from "C". Write the expected visit order before running the code, then verify.
• Compare DFS and BFS visit order on the same graph. Start both from "A" and note how the traversal differs.
• Modify the cycle detection to return the actual cycle (the list of nodes forming the loop).
• Create a graph with multiple disconnected components and run DFS from one node. Which nodes are missed? How would you find all components?

Quick Quiz

Coding Challenge

Real-World Usage

DFS and backtracking algorithms power critical software systems:

• Topological sorting: Build systems (Make, Webpack) use DFS to determine the order to compile files — a file must be built after all its dependencies. DFS post-order gives a valid build sequence.
• Cycle detection: Package managers use DFS to detect circular dependencies (A depends on B, B depends on C, C depends on A) which would cause infinite install loops.
• Maze generation and solving: DFS with backtracking generates random mazes (carve a path deep, backtrack, carve another) and solves them (try each path to its end before trying alternatives).
• Garbage collection: Some garbage collectors use DFS to trace which objects are reachable from root references, marking unreachable objects for deletion.
• Compilers: Analyzing control flow, detecting unreachable code, and optimizing expressions all use DFS-based graph analysis.
• Game AI: Chess engines, puzzle solvers, and pathfinding in strategy games use DFS with pruning to explore possible moves deeply before backtracking.

Connections