Suggest an edit

Improve this article

Refine the answer for “What does the DFS algorithm do on graphs (Depth-First Search)?”. 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

DFS (Depth-First Search) is a graph traversal algorithm that goes as deep as possible along a single path, backtracks when it hits a dead end, and continues with the nearest unvisited vertex. It visits each vertex and edge at most once, runs in O(V+E), and is used for finding paths, checking connectivity, detecting cycles, topological sorting, and more.

## Detailed answer

### What DFS does on graphs

- Traverses the graph in depth: picks a vertex, follows an edge deeper as long as possible, then backtracks.
- Marks vertices as visited, to avoid looping and reprocessing them.
- Produces different traversal orders: preorder (entry), postorder (exit), which are useful, for example, for topological sorting.
- Handles both directed and undirected graphs; also works for trees (a special case of a graph).

### Complexity

- Time: O(V + E), where V is the number of vertices and E the number of edges (each vertex and edge is processed at most once).
- Memory: O(V) to store visited markers and the call stack (recursive) or an explicit stack (iterative).

### Where it is used

- Checking graph connectivity / counting connected components
- Finding paths and ancestors (to reconstruct routes)
- Detecting cycles (in both directed and undirected graphs)
- Topological sorting in a DAG (directed acyclic graph)
- Finding articulation points and bridges, strongly connected components (with modifications)

### How it works (step by step)

1. Pick a starting vertex s (if the graph is disconnected, start from every unvisited vertex).
2. Mark s as visited, perform the needed logic (for example, record it in preorder).
3. Go through every neighbor v of s; if v is not visited, run DFS(v) recursively or via the stack.
4. After processing all neighbors, you can run the post logic (for example, record it in postorder).

### Implementation: recursive (JavaScript)

```javascript
function dfsRecursive(graph, start, visited = new Set(), preorder = [], postorder = []) {
  visited.add(start);
  preorder.push(start); // the moment of entering the vertex
  for (const nei of graph[start] || []) {
    if (!visited.has(nei)) dfsRecursive(graph, nei, visited, preorder, postorder);
  }
  postorder.push(start); // the moment of exiting the vertex
  return { visited, preorder, postorder };
}

// Example: directed graph
// A: B, C; B: D, E; C: F; E: F
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

const { preorder, postorder } = dfsRecursive(graph, 'A');
console.log('preorder:', preorder.join(' -> '));
console.log('postorder:', postorder.join(' -> '));
// Possible output (depends on neighbor order):
// preorder: A -> B -> D -> E -> F -> C
// postorder: D -> F -> E -> B -> C -> A
```

### Implementation: iterative with a stack (JavaScript)

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

while (stack.length) {
    const v = stack.pop();
    if (visited.has(v)) continue;
    visited.add(v);
    order.push(v); // analogous to preorder
    // To make the order closer to the recursive one, we add neighbors to the stack in reverse order
    const neighbors = graph[v] || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const nei = neighbors[i];
      if (!visited.has(nei)) stack.push(nei);
    }
  }
  return order;
}

const order = dfsIterative(graph, 'A');
console.log('iterative order:', order.join(' -> '));
```

### Pre- and post-numbers. Topological sorting

The pre-number (pre) records the moment a vertex is entered, the post-number (post) records the moment it is exited. In a DAG, the topological order can be obtained by recording vertices in postorder and reversing the list.

```javascript
function topoSortDAG(graph) {
  const visited = new Set();
  const post = [];

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

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

console.log('topo:', topoSortDAG(graph).join(' -> '));
```

### Cycle detection

Idea: in a directed graph we color the vertices (0, not visited; 1, on the recursion stack; 2, processed). An edge into a gray vertex (1) means a cycle. In an undirected graph we avoid a "back edge to the parent" by remembering parent.

```javascript
// Cycle in a directed graph
function hasCycleDirected(graph) {
  const color = new Map(); // 0: white, 1: gray, 2: black
  for (const v of Object.keys(graph)) color.set(v, 0);

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

for (const v of Object.keys(graph)) if (color.get(v) === 0 && dfs(v)) return true;
  return false;
}

// Cycle in an undirected graph
function hasCycleUndirected(graph) {
  const visited = new Set();
  function dfs(u, parent = null) {
    visited.add(u);
    for (const v of graph[u] || []) {
      if (!visited.has(v)) {
        if (dfs(v, u)) return true;
      } else if (v !== parent) {
        return true; // found a back edge not to the parent => cycle
      }
    }
    return false;
  }
  for (const v of Object.keys(graph)) if (!visited.has(v) && dfs(v, null)) return true;
  return false;
}
```

### Subtleties and details

- The traversal order is not unique: it depends on the order of neighbors in the adjacency list.
- For a disconnected graph, run DFS from every unvisited vertex to cover all components.
- Deep recursion can overflow the stack (especially in large/elongated graphs). Use the iterative version in such cases.
- Do not forget to mark a vertex visited before the recursive call, otherwise duplicates and/or infinite loops are possible.
- For routing by the smallest number of edges, use BFS, not DFS.

### Summary

DFS is a fundamental tool for working with graphs: fast, simple to implement (recursively or via a stack), gives access to preorder/postorder, lets you find cycles and components, build a topological order, and serves as the foundation for many other algorithms.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.