BFS And DFS Ladder¶
This ladder should make traversal choice feel routine: BFS for unit-weight distance layers, DFS for structure and search-tree reasoning.
Who This Is For¶
Use this ladder if:
- you still blur BFS and DFS together
- you can code them, but not always choose the right one
- traversal order and visited-state bugs still happen often
Warm-Up¶
- connected components
- reachability
- shortest path in an unweighted graph
Target skill:
- use one clean traversal to visit exactly the intended nodes
Core¶
- bipartite check
- cycle detection
- multi-source BFS
Target skill:
- connect traversal invariants to the property being proved
Stretch¶
- parent restoration
- iterative DFS discipline
- traversal order as the base for a later algorithm
Target skill:
- treat BFS/DFS as foundations for stronger graph algorithms, not just standalone tools
Exit Criteria¶
You are ready to move on when:
- you can explain why BFS gives shortest paths in unweighted graphs
- you know when recursive DFS is risky
- you can handle multiple components without state bugs