DSA & Algorithms
Part 15 of 21 · DSA Interview PatternsGraphs — DFS & BFS Traversal — Components, Cycles & Grid Flood
Graph DFS/BFS for components, cycles, bipartite checks, and grid flood fill.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The input is nodes and edges, or a grid that acts like one
Prefer
Visit each node once
DFS explores a component. BFS explores by distance. Both are O(V+E), or O(rows * cols) on a grid.
- Islands are a flood fill that marks land as seen.
- Bipartite fails when a neighbor already has your color.
- Directed cycles need a recursion stack, not only a visited set.
Alternative
A fresh scan with no visited set
That is an infinite loop the moment an undirected edge points backward.
- Forgetting visited.
- Doubling directed edges by habit.
- Dropping the parent when you reconstruct a BFS path.
Pick the frontier
Stack or recursion for DFS. Queue for BFS. Mark seen before you push, not after.
- 1
Start at an unvisited node
A grid start is a land cell you have not flooded. - 2
Choose stack or queue
Distance wants a queue. A component can use either. - 3
Mark seen
On a directed graph, gray means on the current path.
Overview
Graph DFS/BFS for components, cycles, bipartite checks, and grid flood fill.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Model problems as graphs (adjacency list); DFS/BFS for reachability, components, cycles, grid floods.
Recognition cues
- number of islands / flood fill
- clone graph
- course schedule cycle (also topo)
- bipartite coloring
- word ladder (BFS shortest)
Mental model
Decisions
- 1
Step 1 Pick an unvisited start node
- nextStep 2 Need shortest hop counts?
- ?
Step 2 Need shortest hop counts?
- yesStep 3a BFS with a queue - mark visited on enqueue
- noStep 3b DFS with a stack or recursion
- 3
Step 3a BFS with a queue - mark visited on enqueue
- nextStep 4a Distance grows one level at a time
- mark visited on dequeueFailure path - the same node is queued many times
- 4
Step 3b DFS with a stack or recursion
- nextStep 4b Directed graph?
- 5
Step 4a Distance grows one level at a time
- ?
Step 4b Directed graph?
- yesStep 5a Cycle if an edge reaches a node still on the stack
- noStep 5b Cycle if an edge reaches a visited node that is not the parent
- 7
Step 5a Cycle if an edge reaches a node still on the stack
- 8
Step 5b Cycle if an edge reaches a visited node that is not the parent
- 9
Failure path - the same node is queued many times
Lesson map
Graphs — DFS & BFS Traversal — Components, Cycles & Grid Flood
Graph DFS/BFS for components, cycles, bipartite checks, and grid flood fill.
Architecture. Step 1 Pick an unvisited start node Ready. Step 2 Need shortest hop counts? Ready. Step 3a BFS with a queue - mark visited on enqueue Ready. Step 3b DFS with a stack or recursion Ready. Step 4a Distance grows one level at a time Ready. Step 4b Directed graph? Ready. Step 5a Cycle if an edge reaches a node still on the stack Ready. Step 5b Cycle if an edge reaches a visited node that is not the parent Ready. Failure path - the same node is queued many times Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB S["Step 1 Pick an unvisited start node Ready"] K["Step 2 Need shortest hop counts? Ready"] B["Step 3a BFS with a queue - mark visited on enqueue Ready"] D["Step 3b DFS with a stack or recursion Ready"] L["Step 4a Distance grows one level at a time Ready"] C["Step 4b Directed graph? Ready"] G["Step 5a Cycle if an edge reaches a node still on the stack Ready"] P["Step 5b Cycle if an edge reaches a visited node that is not the parent Ready"] F["Failure path - the same node is queued many times Ready"] S -->|continues| K K -->|yes| B K -->|no| D B -->|continues| L D -->|continues| C C -->|yes| G C -->|no| P B -->|mark visited on dequeue| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- O(V+E) time for adj-list DFS/BFS; grid O(RC).
- Space O(V) visited. Grid DFS uses an explicit stack so a large grid does not hit Python's recursion limit.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Number of Islands
- Clone Graph
- Pacific Atlantic Water Flow
- Rotting Oranges
- Word Ladder
- Is Graph Bipartite?
- 01 Matrix
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
DFS vs BFS?
Answer
DFS for components/paths; BFS for unweighted shortest / layers.
Islands?
Answer
DFS/BFS flood each unvisited land cell.
Bipartite?
Answer
2-color with BFS/DFS; conflict means odd cycle.
Word ladder?
Answer
BFS on implicit graph of word mutations.
Visited vs path stack?
Answer
Directed cycle needs in-stack gray nodes.
Grid bounds?
Answer
Always check r,c in range before recurse.