Traversal Techniques
MediumBFS explores in rings, DFS dives
Problem
Compare BFS and DFS traversals of a graph and when to use each.
BFS explores ring by ring; DFS dives deep down one path first.
The idea
BFS uses a queue and reaches every vertex in order of distance, which is why it solves unweighted shortest paths. DFS uses a stack (usually the call stack) and goes deep first, which suits cycle detection, topological order and connectivity questions.
The trick
- BFS for fewest edges; DFS for structure — cycles, components, ordering.
- Both are O(V + E) with a visited set.
- BFS memory scales with the widest level; DFS with the deepest path.
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1
Step 1 of 9. Scan for land. Each unvisited '1' starts a new island; flood-fill its whole blob so it isn't counted twice.
1/9
Optimal
timeO(rows·cols)spaceO(rows·cols)
Sink each island you find.
1for (r, c) if (grid[r][c] === '1') {2 islands++;3 sink(r, c); // DFS marks the blob as water4}5function sink(r, c) {6 if (out of bounds || grid[r][c] !== '1') return;7 grid[r][c] = '0';8 for (const [dr, dc] of DIRS) sink(r+dr, c+dc);9}Input
- grid
- 4 × 4
Memory
- at
- —
- cells marked
- 0
Output
- islands
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- from node 0
- Output:
- visit order
Finished the walkthrough? Add it to your streak.