Graph Traversal

Model the problem as nodes and edges, then traverse: BFS, DFS, and topological sort cover connectivity, ordering, and dependency questions.

Key ideas

  • —Pick a representation first — adjacency list is the default for sparse graphs.
  • —A visited set prevents revisiting nodes and infinite loops on cycles.
  • —Topological sort orders a DAG so every edge points forward; a cycle means no valid order.

Representation and traversal choice

Start by deciding how edges are stored: an adjacency list (a map from node to its neighbors) is compact for the sparse graphs most interview problems use. Then choose a traversal — BFS for shortest hops, DFS for connectivity and recursion-friendly structure. Course Schedule, for instance, is really a graph reachability question dressed up as prerequisites.

Topological sort and cycle detection

When tasks have dependencies, a topological sort produces an order in which every prerequisite comes before the task that needs it. Kahn's algorithm repeatedly removes nodes with no remaining incoming edges; if nodes remain, the graph has a cycle and no valid order exists. This is exactly the test behind detecting impossible course schedules.

Practice this

Sources

← All lessonsNext: Matrix Traversal →