Graph Traversal And Shortest Paths

What's being tested

These problems test graph modeling, BFS/DFS traversal, shortest path under constraints, and connected-component reasoning. Interviewers are checking whether you can convert messy relationships—blocked stops, reporting chains, shared digits, word paths—into nodes, edges, state, and traversal rules.

Patterns & templates

• BFS for unweighted shortest path — use queue, visited, and distance levels; O(V + E) time, O(V) space.

• Dijkstra for weighted or penalty paths — use heapq with (cost, node); needed when dangerous nodes add non-uniform costs.

• Lexicographic shortest path state — optimize (danger_count, steps) instead of one scalar; compare tuples directly in Python.

• DFS/backtracking for path existence — recursively match characters or constraints; mark/unmark visited to avoid cycles without blocking other branches.

• Connected components — build adjacency from shared attributes, then BFS/DFS each unvisited node; useful for grouping two-digit numbers.

• Transitive relationship queries — model manager chains as a directed graph or parent map; use ancestor traversal, caching, or union-like grouping for peers.

• Grid/graph neighbor generation — centralize neighbors(node) logic; filter blocked nodes before enqueueing to avoid invalid states.

Common pitfalls

Pitfall: Treating weighted penalties like ordinary BFS; if costs differ, BFS no longer guarantees the optimal route.

Pitfall: Using one global visited set in backtracking; paths need branch-local state with unmarking on return.

Pitfall: Forgetting disconnected components, duplicate inputs, self-edges, cycles, or “start/end is blocked” edge cases.

Practice these

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