jsschools

Depth-First Search (DFS)

Explores as far as possible along each branch before backtracking; used for cycle detection, topological sort, connected components, and path finding.

Spec ↗

Syntax

dfs(graph, start, visited?)

Parameters

NameTypeRequiredDescription
graph Map<number, number[]> Yes Adjacency list. Keys are node ids, values are neighbour arrays.
start number Yes The node to begin traversal from.
visited Set<number> No Set of already-visited nodes (for multi-component graphs). Created internally if not provided.

Returns

number[] — Nodes in DFS visit order.

Examples

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  const order = [start];
  for (const neighbour of graph.get(start) ?? []) {
    if (!visited.has(neighbour)) {
      order.push(...dfs(graph, neighbour, visited));
    }
  }
  return order;
}

const graph = new Map([
  [0, [1, 2]],
  [1, [3, 4]],
  [2, []],
  [3, []],
  [4, []],
]);
console.log(dfs(graph, 0));
Output 
[ 0, 1, 3, 4, 2 ]

// Iterative DFS (avoids stack overflow for deep graphs)
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const neighbour of (graph.get(node) ?? []).slice().reverse()) {
      if (!visited.has(neighbour)) stack.push(neighbour);
    }
  }
  return order;
}

const graph = new Map([[0,[1,2]],[1,[3]],[2,[4]],[3,[]],[4,[]]]);
console.log(dfsIterative(graph, 0));
Output 
[ 0, 1, 3, 2, 4 ]

Notes

| Case | Time | Space | |---------|----------|--------| | Best | O(V + E) | O(V) | | Average | O(V + E) | O(V) | | Worst | O(V + E) | O(V) | Recursive DFS can hit JS's call stack limit (~10k frames) on deep graphs — prefer the iterative version with an explicit stack. DFS is the foundation for cycle detection (back-edge detection), topological sort (post-order reversal), strongly connected components (Kosaraju, Tarjan), and articulation points/bridges. DFS does NOT guarantee shortest paths in unweighted graphs (use BFS instead).

See also