DFS and Recursion

DFS goes deep: Recursion or explicit stack. Useful for connectivity, cycle detection, and topological sorting in DAGs.

Mark nodes as visited to avoid infinite loops in cycles.

$$O(|V|+|E|)$$

Where used

Cycle detection, topological sorting, Connected Components, maze/constraint search, compiler call graphs. Often uses an explicit stack instead of deep recursion.

Depth

Depth-first search pursues an open branch as far as possible and then returns to the last branching point. Recursion implicitly stores this return state in activation records.

A state array per node prevents re-expansion and makes cycles manageable. With multiple states, active nodes can be distinguished from fully completed nodes, which facilitates cycle detection in directed graphs.

Entry and exit times generate a bracket structure for nested subtrees. This underpins topological sorting, connectivity analysis, and edge classification.

Difficulty levels

1. Follow recursive search sequences for ordered neighbors.
2. Use active and completed states for cycle detection.
3. Connect exit order with topological sorting.

Pitfalls

Excluding only the immediate predecessor is insufficient in general or directed cycles. Large graphs can also exceed the safe recursion depth.