Suggest an edit

Improve this article

Refine the answer for “What is Depth-first search (DFS)?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

Depth-first search (DFS) is an algorithm for traversing graphs and trees that goes as deep as possible along one direction while there are unvisited vertices, then backtracks and continues along the nearest alternative branch. It uses a stack, either implicit (recursion) or explicit. Time complexity is O(V + E), and memory is O(V), accounting for the call stack.

## Detailed explanation

### The idea behind the algorithm

- Start at a starting vertex s, mark it as visited.
- Move to the first unvisited neighbor and repeat the process, going as deep as possible.
- If the current vertex has no unvisited neighbors, backtrack to the previous vertex and look for an alternative branch.
- Repeat until the stack is empty and all reachable vertices have been processed.

### Recursive vs iterative variant

- Recursive: simpler to write and read; the call stack acts as the traversal stack.
- Iterative: an explicit stack (an array/Stack structure). Gives better control over depth and avoids call-stack overflow.
- The visit order depends on the order of the neighbors and how you push them onto the stack.

### Tree traversal orders

- Preorder (NLR): the node first, then the left subtree, then the right.
- Inorder (LNR): left, node, right (important for a BST, it gives a sorted order).
- Postorder (LRN): left, right, node (used for deleting/freeing resources).

### Complexity

- Time: O(V + E), where V is the number of vertices and E is the number of edges.
- Memory: O(V) for visited plus O(H) for the stack depth (H ≤ V). O(V) in the worst case.

### Where it's used

- Checking reachability and finding a path between vertices.
- Finding connected components (in undirected graphs).
- Cycle detection (especially in directed graphs, via colors/the recursion stack).
- Topological sorting (DAG), using a postorder.
- Backtracking problems: generating combinations/permutations, Sudoku, N-Queens.
- Traversing a grid/maze (for example, counting "islands").

### Pitfalls and tips

- Don't forget visited: without it you'll get an infinite loop when cycles exist.
- Deep recursion can overflow the stack: choose the iterative variant or raise the limit if possible.
- Neighbor order affects the specific visit order, but not the correctness of results for classes of problems (for example, reachability/components).
- To visit all vertices in a disconnected graph, run DFS starting from each unvisited vertex.

### How to answer in an interview

- Give a definition: "goes as deep as possible, then backtracks; uses a stack/recursion."
- State the complexity: time O(V+E), memory O(V).
- Mention visited and handling cycles, and the recursive and iterative variants.
- Give 1-2 applications: topological sorting, reachability checks, islands on a grid.

## Code examples

### DFS on a graph (recursive)

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

dfsRecursive(graph, 'A', v => console.log('visit', v));
```

### DFS on a graph (iterative, with a stack)

```javascript
function dfsIterative(graph, start, visit = () => {}) {
  const visited = new Set();
  const stack = [start];
  while (stack.length) {
    const v = stack.pop();
    if (visited.has(v)) continue;
    visited.add(v);
    visit(v);
    const neighbors = graph[v] || [];
    // To match recursion's order, push neighbors onto the stack in reverse
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const nei = neighbors[i];
      if (!visited.has(nei)) stack.push(nei);
    }
  }
  return visited;
}

// Usage example:
// dfsIterative(graph, 'A', v => console.log('visit', v));
```

### Finding a path between two vertices (DFS)

```javascript
function dfsPath(graph, start, target) {
  const visited = new Set();
  const parent = new Map();
  let found = false;

dfs(start);
  if (!found) return null;
  const path = [];
  for (let v = target; v != null; v = parent.get(v)) path.push(v);
  path.reverse();
  return path;
}

console.log(dfsPath(graph, 'A', 'F')); // For example: [ 'A', 'B', 'E', 'F' ]
```

### DFS on a tree: preorder / inorder / postorder

```javascript
class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new Node(1,
  new Node(2, new Node(4), new Node(5)),
  new Node(3)
);

function preorder(node, visit) {
  if (!node) return;
  visit(node.val);
  preorder(node.left, visit);
  preorder(node.right, visit);
}

function inorder(node, visit) {
  if (!node) return;
  inorder(node.left, visit);
  visit(node.val);
  inorder(node.right, visit);
}

function postorder(node, visit) {
  if (!node) return;
  postorder(node.left, visit);
  postorder(node.right, visit);
  visit(node.val);
}

preorder(root, v => console.log('pre', v));   // 1,2,4,5,3
inorder(root, v => console.log('in', v));     // 4,2,5,1,3
postorder(root, v => console.log('post', v)); // 4,5,2,3,1
```

### DFS on a grid (counting the number of "islands")

```javascript
function numIslands(grid) {
  const m = grid.length;
  const n = grid[0]?.length || 0;
  const seen = Array.from({ length: m }, () => Array(n).fill(false));
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

function dfs(r, c) {
    if (r < 0 || c < 0 || r >= m || c >= n) return;
    if (seen[r][c] || grid[r][c] !== '1') return;
    seen[r][c] = true;
    for (const [dr, dc] of dirs) dfs(r + dr, c + dc);
  }

let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (!seen[r][c] && grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

const grid = [
  ['1','1','0','0'],
  ['1','0','0','1'],
  ['0','0','1','1'],
];
console.log(numIslands(grid)); // 3
```

### Cycle detection and topological sorting (DAG)

```javascript
function hasCycleDirected(graph) {
  const color = new Map(); // 0=white,1=gray,2=black
  const nodes = Object.keys(graph);

function dfs(v) {
    color.set(v, 1);
    for (const nei of graph[v] || []) {
      const c = color.get(nei) || 0;
      if (c === 1) return true; // back edge => cycle
      if (c === 0 && dfs(nei)) return true;
    }
    color.set(v, 2);
    return false;
  }

for (const v of nodes) {
    if ((color.get(v) || 0) === 0 && dfs(v)) return true;
  }
  return false;
}

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

function dfs(v) {
    visited.add(v);
    for (const nei of graph[v] || []) {
      if (!visited.has(nei)) dfs(nei);
    }
    order.push(v); // postorder
  }

for (const v of Object.keys(graph)) {
    if (!visited.has(v)) dfs(v);
  }
  order.reverse();
  return order;
}

// Example:
const dag = {
  A: ['C'],
  B: ['C', 'D'],
  C: ['E'],
  D: ['F'],
  E: ['H', 'F'],
  F: ['G'],
  G: [],
  H: []
};

console.log('hasCycle', hasCycleDirected(dag)); // false
console.log('topo', topoSort(dag)); // one of the valid orders
```

### Summary

DFS is a simple and powerful fundamental algorithm. It traverses a graph/tree by going as deep as possible, relies on a stack (explicit or recursive), has linear complexity O(V+E), and is widely used: from path finding and components to topological sorting and backtracking problems. The key points: correctly maintain visited and account for stack depth.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1187 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.