What does the DFS algorithm do on graphs (Depth-First Search)?

AlgorithmsJunior~3 min read

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)

Pick a starting vertex s (if the graph is disconnected, start from every unvisited vertex).
Mark s as visited, perform the needed logic (for example, record it in preorder).
Go through every neighbor v of s; if v is not visited, run DFS(v) recursively or via the stack.
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.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.