Depth-First Search

Master recursive and iterative DFS and use three-color (white/gray/black) vertex marking to detect cycles in directed graphs in O(V+E) time.

5 min read Level 3/5 #dsa#graph#dfs

What you'll learn

Implement DFS both recursively and iteratively on an adjacency list
Explain white/gray/black color marking and what a gray-to-gray edge means
Detect cycles in a directed graph using DFS coloring

Depth-First Search (DFS) follows each path as far as possible before backtracking. It powers cycle detection, topological sort, strongly connected components, and maze solving.

Recursive DFS

The cleanest form mirrors the call stack directly. Use a Set for visited nodes when cycles don’t matter; use color marking when they do.

// graph: Map<number, Set<number>>
function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);

  for (const neighbour of graph.get(start) ?? []) {
    if (!visited.has(neighbour)) {
      dfs(graph, neighbour, visited);
    }
  }
}

Iterative DFS

When recursion depth could hit JavaScript’s stack limit (large graphs), use an explicit stack. Note that iterative DFS visits neighbours in reverse order compared to the recursive version.

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

  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);

    for (const neighbour of graph.get(node) ?? []) {
      if (!visited.has(neighbour)) stack.push(neighbour);
    }
  }
  return order;
}

Cycle Detection via Three-Color Marking

In a directed graph, a cycle exists if DFS finds a back edge — an edge to a vertex that is currently on the recursion stack. The three colors represent:

white (0) — not yet visited
gray (1) — currently in the recursion stack
black (2) — fully explored

An edge from a gray node to another gray node is a back edge, which means a cycle.

const WHITE = 0, GRAY = 1, BLACK = 2;

function hasCycle(graph, numVertices) {
  const color = new Array(numVertices).fill(WHITE);

  function dfsColor(v) {
    color[v] = GRAY;
    for (const w of graph.get(v) ?? []) {
      if (color[w] === GRAY) return true;  // back edge → cycle
      if (color[w] === WHITE && dfsColor(w)) return true;
    }
    color[v] = BLACK;
    return false;
  }

  for (let v = 0; v < numVertices; v++) {
    if (color[v] === WHITE && dfsColor(v)) return true;
  }
  return false;
}

Complexity

Metric	Value	Reason
Time	O(V+E)	Each vertex and edge visited once
Space	O(V)	Color array and recursion stack

Up Next

DFS finish times give us topological ordering of a DAG — learn Kahn’s algorithm and the DFS-based approach.

Topological Sort →