Depth-First Search (DFS): A Complete Guide

Depth-First Search, commonly known as DFS, is one of the most important graph traversal algorithms in computer science. It explores a graph by going as deep as possible along each branch before backtracking.

DFS is widely used in many algorithmic problems including maze solving, cycle detection, topological sorting, and generating combinations or permutations.

Understanding the Intuition

Imagine exploring a maze. Instead of checking every nearby corridor first, you follow one path as far as possible. If you reach a dead end, you go back to the previous junction and try another path.

This is exactly how DFS works: it dives deep into a branch of the graph before exploring alternative paths.

How DFS Works

DFS can be implemented using either recursion or an explicit stack data structure. The algorithm keeps track of visited nodes to avoid revisiting them.

1. Start from a chosen node
2. Mark the node as visited
3. Explore one unvisited neighbor
4. Continue exploring deeper until no unvisited neighbors remain
5. Backtrack to the previous node and explore another branch

Example Traversal

Suppose node A connects to B and C. Node B connects to D and E. DFS would visit nodes in the following order:

1. Start at A
2. Go to B
3. Go to D
4. Backtrack to B
5. Go to E
6. Backtrack to A
7. Go to C

JavaScript Implementation

function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  console.log(node);

  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

Time Complexity

DFS visits each vertex once and inspects each edge once. Therefore its time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

Space Complexity

The space complexity depends on the recursion depth or stack size. In the worst case it can reach O(V).

Common Applications

• Cycle detection in graphs
• Topological sorting
• Maze solving algorithms
• Connected components detection
• Backtracking problems

Conclusion

Depth-First Search is a powerful algorithm that forms the foundation of many advanced techniques. Understanding DFS is essential for mastering graph algorithms and solving complex algorithmic challenges.