38. Depth First Search (DFS)

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

Concept: Going Deep

Imagine navigating a maze. DFS is like going down one path until you hit a dead end, then returning (backtracking) and trying the next available path.

DFS typically uses a Stack (or recursion, which uses the call stack) to remember which nodes to visit next.

Algorithm Steps (Recursive)

1. Start at a source node S.
2. Mark S as visited.
3. For every neighbor V of S:
   • If V is not visited, recursively call DFS on V.

Use Cases

• Finding connected components.
• Detecting cycles in a graph.
• Topological sorting.