DFS (Depth-First Search) Traversal Explained

Depth-First Search (DFS)

Depth-First Search explores a graph by following one path as far as possible before backtracking. It dives deep into the graph before exploring siblings, which makes it fundamentally different from BFS.

How DFS Works

1. Initialize — Push the starting node onto a stack (or call the function recursively) and mark it as visited.
2. Pop — Remove the top node from the stack. This is the current node.
3. Explore — For each unvisited neighbor, push it onto the stack and mark it.
4. Backtrack — When a node has no unvisited neighbors, the algorithm backtracks to the previous node.
5. Repeat — Continue until the stack is empty.

Stack: [A]         → Visit A, push B, C
Stack: [B, C]      → Visit C, push E
Stack: [B, E]      → Visit E (no unvisited neighbors)
Stack: [B]         → Visit B, push D
Stack: [D]         → Visit D
Stack: []          → Done

Discovery and Finish Times

In recursive DFS, each node gets two timestamps:

• Discovery time — when the node is first visited
• Finish time — when all descendants have been fully explored

These timestamps are crucial for classifying edges (tree, back, forward, cross) and for algorithms like topological sort.

Time and Space Complexity

• Time: O(V + E)
• Space: O(V) for the visited set and the call stack (or explicit stack)

Applications

DFS powers many important graph algorithms:

• Cycle detection — A back edge (an edge to an ancestor) indicates a cycle
• Topological sorting — Reverse finish-time ordering gives a valid topological order
• Connected components — Run DFS from each unvisited node to find all components
• Strongly connected components — Kosaraju's or Tarjan's algorithm builds on DFS