BFS, DFS, And Shortest Path Search

What's being tested

Demonstrate graph traversal skills: model grids/structures as graphs, pick the right search (unweighted vs weighted), and implement correct distance/reachability. Interviewers probe correct state representation, complexity reasoning, and edge-case handling like obstacles, multiple sources, and cycles.

Patterns & templates

• BFS on unweighted graphs/grids — use deque, visited, and parent map; distances in O(V+E) time and O(V) space.

• Multi-source BFS — enqueue all sources with distance 0 to compute nearest-source distances in one pass.

• Dijkstra for non-negative weights — use priority_queue (min-heap); complexity O((V+E) log V).

• 0-1 BFS when weights are 0/1 — use deque to get O(V+E) time without a heap.

• A* heuristic search — admissible heuristic (e.g., Manhattan) to speed grid shortest-paths while preserving optimality.

• State representation — encode position and extra state (keys, direction) as tuples/ints; canonicalize to avoid duplicates.

• Path reconstruction — store parent[node] during search; reconstruct by backtracking to avoid re-traversal costs.

Common pitfalls

Pitfall: Treating a grid cell as visited before considering better paths — in weighted graphs you must allow distance relaxation (use Dijkstra).

Pitfall: Forgetting diagonal vs orthogonal neighbor rules — clarify movement model and neighbor generation deltas.

Pitfall: Not bounding memory for large N — represent visited compactly (bitset/flattened index) for big grids.