Depth-First Search

Depth-First Search

If BFS is like exploring a maze floor by floor, Depth-First Search (DFS) is like picking a path and following it as far as you can before backtracking. It's the adventurous approach — go deep first, then explore alternatives.

DFS uses a stack (LIFO) or recursion to keep track of vertices. It's like a stack of plates — you always take the top one. This gives DFS its go-deep-before-wide behavior.

How DFS Works

Start at a vertex, mark it as visited, and then recursively visit each unvisited neighbor. Keep going deeper until you hit a dead end, then backtrack to the last vertex with unvisited neighbors.

DFS is great for exploring all possible paths or checking if a path exists between two vertices. It's also the foundation for many graph algorithms like topological sort and cycle detection.

function dfs(graph, vertex, visited = new Set()) {
  visited.add(vertex);
  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
  return visited;
}

Traversal Orders

DFS can be implemented in different orders depending on when you process the vertex. Pre-order processes the vertex before visiting neighbors — like meeting someone before exploring their friends.

Post-order processes the vertex after all neighbors are visited — like saying goodbye to everyone before leaving a party. Both are useful in different scenarios.

function dfsPreOrder(graph, vertex, visited = new Set()) {
  visited.add(vertex);
  console.log(vertex);
  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      dfsPreOrder(graph, neighbor, visited);
    }
  }
}

Cycle Detection

One powerful use of DFS is detecting cycles in a graph. If during DFS you encounter a vertex that's already in the current recursion stack, you've found a cycle. It's like realizing you've walked in a circle!

This is crucial for many applications — detecting infinite loops in dependency graphs, checking if a task scheduling system has circular dependencies, or validating that a graph is a DAG (Directed Acyclic Graph).

function hasCycle(graph, vertex, visited, recStack) {
  visited.add(vertex);
  recStack.add(vertex);
  
  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      if (hasCycle(graph, neighbor, visited, recStack)) {
        return true;
      }
    } else if (recStack.has(neighbor)) {
      return true;
    }
  }
  recStack.delete(vertex);
  return false;
}