Graph Traversal, Shortest Paths, and Topological Sort

What's being tested

Tests whether you can model arrays, grids, and similarity relationships as graphs, then choose the right traversal: BFS for unweighted shortest paths, DFS/Union-Find for components, Dijkstra-style ordering for weighted or multi-criteria paths, and topological sort for dependency DAGs. Interviewers look for correctness under constraints: blocked nodes, dangerous nodes, tie-breaking, revisits, and large input sizes.

Patterns & templates

• BFS shortest path on unweighted graphs — queue (node, dist), visited on enqueue, O(V + E) time and space.

• Constrained BFS with blocked nodes — skip neighbors in blocked before enqueue; validate source/target edge cases before traversal.

• Multi-criteria shortest path — use heapq with tuple (danger_count, steps, node); equivalent to Dijkstra over lexicographic costs.

• Connected components — run DFS/BFS from each unvisited node; count or track max component size in O(V + E).

• Grid traversal — convert (r, c) to implicit neighbors via dirs; bounds-check before accessing cells; mark visited immediately.

• Top-K graph ranking — BFS by distance, collect candidates, sort by (distance, -rating, id) or maintain bounded heap for scale.

• Topological sort — use indegree + queue for Kahn’s algorithm; if output length < V, report cycle, O(V + E).

Common pitfalls

Pitfall: Marking nodes visited when popped instead of when enqueued can duplicate work and break shortest-path assumptions in dense graphs.

Pitfall: Using plain BFS when the optimization is lexicographic, such as minimizing dangerous stops before minimizing total steps.

Pitfall: Forgetting disconnected graphs, blocked start/end nodes, self-loops, duplicate edges, and deterministic tie-breaking for ranked output.

Practice these

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