DFS

Overview

Depth-First Search is a graph traversal algorithm that explores as far as possible along each branch before backtracking. DFS uses recursion or a stack to dive deep into the graph before exploring other paths.

How DFS Works

DFS starts at a source vertex, marks it as visited, and recursively visits all unvisited neighbors. For each neighbor, it immediately explores that neighbor's neighbors before returning. This creates a deep exploration pattern.

Recursive Implementation

The recursive approach naturally uses the call stack to remember where to backtrack. Each recursive call explores one neighbor deeply, and when all neighbors are explored, the function returns to explore other branches from previous levels.

Stack-Based Implementation

DFS can also use an explicit stack instead of recursion. Push the starting vertex, then while the stack isn't empty, pop a vertex, mark it visited, and push all unvisited neighbors. This mimics the recursive call stack.

Applications of DFS

DFS is useful for finding connected components, detecting cycles in graphs, topological sorting of directed acyclic graphs, solving maze problems, and finding paths between vertices. It's also the foundation for many advanced algorithms.

Time and Space Complexity

Like BFS, DFS has O(V + E) time complexity as it visits each vertex once and checks each edge once. Space complexity is O(V) for the recursion stack or explicit stack, plus the visited tracking.