Depth-First Search — Recursive and Iterative Patterns
Understand DFS as a flexible template for exploring as far as possible, powering cycle detection, connected components, and backtracking.
Problem Statement
Develop a reliable DFS template so you can traverse graphs recursively or iteratively, detect cycles, and build sophisticated searches such as backtracking and topological sorts.
Why This Problem Matters
- DFS underlies flood fill problems, island counters, and spanning trees; once comfortable, you can pivot quickly to variations.
- It doubles as a backtracking engine when you combine it with path lists and undo steps.
- Recursive reasoning tests your ability to define invariants, base cases, and stack depth constraints.
Thought Process
Decide between recursion and an explicit stack
Recursion keeps the code concise but may hit call-stack limits; mention the trade-off early to show awareness.
Mark visited before diving deeper
Prevents infinite loops on cyclic graphs and keeps time linear.
Layer extra bookkeeping for the goal
Need discovery/finish times? Track timestamps. Need path restoration? Maintain parent pointers. Need cycle detection? Track recursion stack.
Step-by-Step Reasoning
- Pick a starting node and mark it visited.
- For each neighbor, if unseen, recurse (or push onto a stack) and keep exploring.
- Process post-order logic after returning (e.g., add to topological order).
- Repeat for every disconnected component.
Dry Run
Graph: 1 → 2 → 3, 2 → 4
Recursive DFS visits 1, 2, 3, backtracks, then explores 4. Post-order adds nodes in reverse finish time.
Matrix island count
DFS spreads through adjacent land cells marking them visited so each island is counted exactly once.
Complexity Analysis
Time
O(V + E)
Space
O(V)
Why
Each vertex and edge is touched once. Recursion depth can reach V in the worst case (skewed graph).
Annotated Solution
import java.util.*;
public class DepthFirstTraversal {
public static List<Integer> dfs(Map<Integer, List<Integer>> adjList, int start) {
List<Integer> order = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
explore(adjList, start, visited, order);
return order;
}
private static void explore(Map<Integer, List<Integer>> adjList, int node,
Set<Integer> visited, List<Integer> order) {
if (!visited.add(node)) {
return;
}
order.add(node);
for (int neighbor : adjList.getOrDefault(node, Collections.emptyList())) {
explore(adjList, neighbor, visited, order);
}
}
}A recursive helper keeps the call stack aligned with the traversal order. Swapping to an explicit array stack is a trivial change if recursion depth is a concern.
Common Pitfalls
- Forgetting to mark visited before recursing can create infinite loops on cycles.
- Mutating shared state without cloning during backtracking leads to corrupted paths.
- Ignoring disconnected components causes missed nodes; wrap DFS calls in a loop over all vertices.
Follow-Up Questions
- Enhance DFS to record discovery/finish timestamps for Kosaraju’s strongly connected components.
- Convert recursion to an explicit stack to avoid call-stack limits and show iterative control.
- Pair DFS with memoisation to transition into dynamic programming on DAGs.