BFS, DFS, Graph, And Grid Traversal

What's being tested

Graph traversal fluency: modeling matrices, grids, nested structures, and dependency lists as nodes plus edges, then choosing BFS for shortest paths or DFS for exhaustive exploration. Interviewers are probing correctness under edge cases, clean implementation, and complexity reasoning: $O(V+E)$ for graphs, $O(RC)$ for grids.

Patterns & templates

• Grid DFS component sizing — iterate every cell, launch dfs(r,c) on unvisited valid cells, count region size; O(RC) time, O(RC) worst stack.

• Iterative DFS with stack — safer than recursion for large matrices; mark visited when pushing, not popping, to avoid duplicates.

• BFS shortest path — use deque, level distance, and optional parent[(r,c)] map for reconstruction; handles obstacles and unweighted moves.

• Cycle detection in directed graphs — use WHITE/GRAY/BLACK states in dfs(node); encountering GRAY means cycle, postorder gives topological order.

• Adjacency construction — for dependency/order problems, build dict[node] -> list[neighbors]; include isolated nodes so output size is correct.

• Bounds helper — centralize in_bounds(r,c) and DIRS = [(1,0),(-1,0),(0,1),(0,-1)]; clarify whether diagonals count.

• Nested DFS aggregation — pass depth into recursion for depth-weighted sums; watch for empty lists and mixed integer/list nodes.

Common pitfalls

Pitfall: Using DFS for shortest path in an unweighted grid. DFS may find a path, but BFS guarantees minimum distance.

Pitfall: Marking grid cells visited too late. If multiple neighbors enqueue the same cell, runtime and parent reconstruction can break.

Pitfall: Forgetting recursion-depth limits. In Python, a long chain or huge connected region can exceed the call stack; switch to iterative traversal.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.