Depth-First Search

Depth-First Search

Depth-First Search (DFS) explores a graph by going as deep as possible before backtracking. It follows each path to its end before trying alternatives. DFS uses a stack — either an explicit one or the call stack via recursion.

Algorithm (Recursive)

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

  function visit(node) {
    visited.add(node);
    result.push(node);
    for (const neighbor of (graph[node] || [])) {
      if (!visited.has(neighbor)) visit(neighbor);
    }
  }

  visit(start);
  return result;
}

BFS vs DFS

Real-World Uses

• Cycle detection in directed graphs (e.g., detecting circular dependencies).
• Topological sort for build systems and task scheduling.
• Maze solving — go deep until you hit a dead end, then backtrack.
• Tree traversals — pre-order, in-order, post-order are all DFS variants.
• Connected components — find all nodes reachable from a source.

Your Task

Implement dfs(graph, start) that returns an array of nodes visited in DFS order using recursion.