11.2 Depth-First Search (DFS) Algorithm

Depth-First Search (DFS) Algorithm

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Where BFS fans out level by level, DFS dives deep down one path, only turning around when it hits a dead end. This makes it naturally suited for problems like cycle detection, topological sorting, and pathfinding through maze-like structures.

DFS can be implemented recursively or iteratively using a stack. Either way, the time complexity is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges.

DFS Algorithm Fundamentals

The core idea of DFS: pick a starting vertex, visit it, then immediately move to one of its unvisited neighbors. Keep going deeper until you reach a vertex with no unvisited neighbors, then backtrack to the most recent vertex that still has unexplored paths.

• Works on both directed graphs (edges have a direction) and undirected graphs (edges go both ways)
• Uses a stack data structure to track which vertex to visit next. The recursive version uses the call stack implicitly; the iterative version uses an explicit stack.
• Requires a visited set (or boolean array) to avoid revisiting vertices and getting stuck in infinite loops

Think of it like navigating a maze: you pick a direction and keep walking until you hit a wall, then retrace your steps to the last intersection where you had an untried path.

Stack-Based and Recursive DFS Implementation

Recursive implementation:

1. Mark the current vertex as visited.
2. For each unvisited neighbor of the current vertex, recursively call DFS on that neighbor.
3. The base case is implicit: when a vertex has no unvisited neighbors, the function returns and the call stack handles backtracking for you.

</>Code
DFS(vertex, visited):
    visited.add(vertex)
    for each neighbor of vertex:
        if neighbor not in visited:
            DFS(neighbor, visited)

Iterative implementation using an explicit stack:

1. Create a stack and push the starting vertex onto it.
2. While the stack is not empty:
   1. Pop a vertex from the top of the stack.
   2. If that vertex has not been visited, mark it as visited.
   3. Push all of its unvisited neighbors onto the stack.

One thing to watch: the iterative version may visit neighbors in a different order than the recursive version, since pushing all neighbors onto the stack reverses the order they get processed. If traversal order matters, push neighbors in reverse order.

Time and Space Complexity of DFS

Time complexity: $O(V + E)$

Every vertex is visited at most once, and every edge is examined at most once (twice for undirected graphs, but that's still proportional to $E$). This is the same time complexity as BFS.

Space complexity: $O(V)$

• The visited structure takes $O(V)$ space.
• In the worst case, the stack (explicit or call stack) can hold up to $V$ vertices. This happens when the graph is a long chain with no branching, so DFS goes all the way deep before any backtracking.
• For the recursive version, a very deep graph can cause a stack overflow if $V$ is large. The iterative version avoids this by using heap-allocated memory for the explicit stack.

Applications of DFS in Graph Problems

Cycle detection is one of the most common uses. During DFS on an undirected graph, if you encounter an edge leading to a vertex that's already been visited (and it's not the vertex you just came from), a cycle exists. For directed graphs, cycle detection uses a "recursion stack" or coloring scheme to track vertices currently being explored.

Topological sorting applies to directed acyclic graphs (DAGs). You run DFS and record vertices in reverse order of completion. The result is a valid ordering where every edge points from an earlier vertex to a later one. Course prerequisite chains are a classic example: if Course A must come before Course B, A appears earlier in the topological order.

Finding connected components: In an undirected graph, running DFS from an unvisited vertex discovers all vertices in that component. Repeat from the next unvisited vertex to find the next component. For directed graphs, algorithms like Kosaraju's or Tarjan's use DFS to find strongly connected components, which are maximal subsets of vertices where every vertex is reachable from every other vertex.

Pathfinding and exhaustive search: DFS naturally explores all possible paths from a source, making it useful for problems that require examining every configuration. Maze solving, puzzle states (like solving a Sudoku board), and generating all permutations are typical examples. Note that DFS does not guarantee the shortest path, so use BFS when shortest paths matter.