Day 10 — Graph Traversal (DFS & BFS)

Two algorithms. That’s all you really need to navigate any graph: DFS (go deep) and BFS (go wide). Everything more complicated — shortest paths, cycle detection, topological sort, connected components, bipartite check — is one of these two with a small tweak.

If Day 9 was about the model, today is about the motion. We give the graph a starting node and watch the algorithm walk it.

What you’ll learn today

• DFS — go as deep as possible along one path, then backtrack. The recursive sibling of tree traversal.
• BFS — explore layer by layer using a queue. The natural fit for “shortest path on an unweighted graph.”
• The visited set pattern that turns infinite loops into termination on graphs with cycles.
• The mental rule for picking DFS vs BFS based on the question.
• The pattern family — connected components, flood fill, cycle detection, bipartite check, multi-source BFS, topological sort, 0-1 BFS — all variations on the same two algorithms.
• Warm-up exercises that drill the templates before the harder problems.
• Ten interview classics: Number of Islands, Clone Graph, Course Schedule, Max Area of Island, Word Ladder, Pacific Atlantic Water Flow, Walls and Gates, Surrounded Regions, Is Graph Bipartite, Shortest Path in Binary Matrix.

You’ve already seen both — in disguise

• DFS = recursion on graphs. Day 5 was DFS on call-stack frames. The tree-traversal problems on Day 6 (Same Tree, Symmetric Tree, Balanced Tree) were DFS in miniature — the only difference is trees can’t loop back, so we didn’t need a visited set.
• BFS = the queue from Day 4 processing nodes one layer at a time. The Rotting Oranges practice problem you solved was multi-source BFS.

Today is the moment those two concepts get their proper names and become the building blocks of an entire chapter of algorithms.

Roadmap

1. DFS — recursive and iterative templates, visited tracking, on grids vs adjacency lists, two complete walkthroughs.
2. BFS — queue-based template, level-by-level processing, shortest-path-on-unweighted-graphs trick.
3. DFS vs BFS — the decision guide: which to reach for given the question.
4. Patterns — the family of DFS/BFS variations: connected components, flood fill, cycle detection, bipartite check, multi-source BFS, topological sort, 0-1 BFS.
5. Basic Questions — warm-up exercises: implement DFS from scratch, trace BFS layers, identify the right algorithm for a given prompt.
6. Practice Questions — ten interview classics covering both algorithms across grid, graph, and word problems.