2.4 BFS & DFS — DSA Crash Course

Deep Dive: Watch the Traversal Unfold

Beginner tip: BFS and DFS are two ways to explore a maze. BFS (Breadth-First) explores one step in every direction before going deeper -- like ripples in water. It always finds the shortest path. DFS (Depth-First) follows one path as far as possible before backtracking -- like solving a maze by hugging the left wall. Use BFS for "shortest" and DFS for "explore everything."

BFS vs DFS Order — Visual

Same graph, two traversal orders. Numbers on each node show the visit order.

BFS (level-by-level) — visits all neighbours of node 1 before going deeper:

graph TD
  A((1: A))
  B((2: B))
  C((3: C))
  D((4: D))
  E((5: E))
  F((6: F))
  G((7: G))
  A --> B
  A --> C
  B --> D
  B --> E
  C --> F
  C --> G

DFS (deep-first) — chases each branch to its end before backtracking:

graph TD
  A((1: A))
  B((2: B))
  D((3: D))
  E((4: E))
  C((5: C))
  F((6: F))
  G((7: G))
  A --> B
  A --> C
  B --> D
  B --> E
  C --> F
  C --> G

BFS -- Rotting Oranges (Multi-Source BFS)

Grid at time 0:        time 1:          time 2:          time 3:
2  1  1                2  2  1          2  2  2          2  2  2
1  1  0       ->       2  1  0   ->     2  2  0   ->     2  2  0
0  1  1                0  1  1          0  2  1          0  2  2

day 0 queue: [(0,0)]           -> rot (0,1),(1,0)
day 1 queue: [(0,1),(1,0)]     -> rot (0,2),(1,1)
day 2 queue: [(0,2),(1,1)]     -> rot (2,1)
day 3 queue: [(2,1)]           -> rot (2,2)
day 4 queue: [(2,2)]           -> no fresh neighbors
Answer: 4 minutes

All rotten oranges spread SIMULTANEOUSLY each minute -- that is multi-source BFS. Push ALL initial sources into the queue before starting.

DFS -- Number of Islands (Flood Fill)

Grid:                After DFS from (0,0):   After DFS from (2,2):
1 1 0 0 0            0 0 0 0 0               0 0 0 0 0
1 1 0 0 0     ->     0 0 0 0 0        ->     0 0 0 0 0
0 0 1 0 0            0 0 1 0 0               0 0 0 0 0
0 0 0 1 1            0 0 0 1 1               0 0 0 1 1

Island 1: DFS sinks all connected 1s to 0.
Island 2: found at (2,2), DFS sinks it.
Island 3: found at (3,3), DFS sinks connected (3,4).
Total: 3 islands.

Key insight: DFS is a "sink" operation. Once you visit a cell, mark it so you never count it again. Each new DFS start = one new island.

When BFS vs DFS

  BFS                              DFS
  Queue (FIFO)                     Stack / Recursion (LIFO)
  Level-by-level                   Deep-then-backtrack
  SHORTEST path (unweighted)       ALL paths / exhaustive
  More memory (stores full level)  Less memory (one path at a time)

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About BFS & DFS

The Decision

Want This?	Use
Shortest path (unweighted)	BFS
Level-by-level processing	BFS
All paths / exhaustive search	DFS
Detect cycles	DFS (with coloring)
Topological order	DFS (post-order) or BFS (Kahn's)

BFS Mental Model

Imagine dropping a stone in water. Ripples expand outward equally.
BFS visits ALL nodes at distance 1, then ALL at distance 2, etc.
First time you reach a node = shortest path to it.

Implement with a QUEUE:
  Add start -> process all at level 0 -> add their neighbors -> process level 1...

BFS Template

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = {start}
    level = 0
    while queue:
        for _ in range(len(queue)):  # process one level
            node = queue.popleft()
            for neighbor in get_neighbors(node):
                if neighbor not in visited:
                    visited.add(neighbor)  # mark BEFORE adding
                    queue.append(neighbor)
        level += 1

DFS Mental Model

Imagine walking a maze: go as DEEP as possible down one path.
Hit a dead end? Backtrack and try the next path.
Repeat until all paths explored.

Implement with RECURSION (implicit stack) or explicit STACK.

DFS Template

def dfs(node, visited):
    visited.add(node)
    for neighbor in get_neighbors(node):
        if neighbor not in visited:
            dfs(neighbor, visited)

Multi-Source BFS -- Seed the Queue with Everything at Once

Some problems ask "shortest distance from any source" -- e.g., Rotting Oranges (minutes until every fresh orange has a rotten neighbor) or 01 Matrix (distance from each cell to the nearest 0). Running BFS once per source is O(sources * (V + E)) and almost always TLEs.

The trick is a one-line change to the standard BFS template: instead of seeding the queue with a single start, seed it with every source at distance 0. The wave then expands from all of them simultaneously.

from collections import deque

def multi_source_bfs(grid, sources):
    queue = deque(sources)              # <-- the only change vs single-source BFS
    visited = set(sources)
    while queue:
        r, c = queue.popleft()
        for nr, nc in neighbors(r, c):
            if (nr, nc) not in visited and is_valid(nr, nc):
                visited.add((nr, nc))
                queue.append((nr, nc))

For 01 Matrix, sources is "every cell containing 0" and you track distance per cell as you pop. For Rotting Oranges, sources is "every initially rotten orange" and the BFS level count is the answer (minutes elapsed).

Why this works: BFS guarantees that the first time a cell is reached, it is reached by the shortest path from the nearest entry in the queue. If multiple sources sit in the queue at distance 0, "nearest entry" naturally means "nearest source." One pass, total cost O(V + E) regardless of how many sources you have.

When You See a Graph/Grid Traversal, Ask Yourself

1. "Shortest path" or "minimum steps"? -> BFS
2. "Can I reach from A to B?" -> DFS (simpler) or BFS
3. "Count islands / connected components"? -> DFS from each unvisited, count
4. "Multiple starting points spreading"? -> Multi-source BFS
5. "All possible paths"? -> DFS backtracking

Common Mistakes

BFS: Adding to queue without marking visited first -> duplicates, TLE
DFS: Not marking visited -> infinite loop on cycles
Grid problems: forgetting boundary checks 0 <= r < rows and 0 <= c < cols

Problems

#	Problem	BFS/DFS	Status
1	Number of Islands	DFS flood fill	[ ]
2	Word Ladder	BFS (shortest)	[ ]
3	Clone Graph	BFS/DFS + HashMap	[ ]
4	Rotting Oranges	Multi-source BFS	[ ]
5	Surrounded Regions	Border DFS	[ ]
6	01 Matrix	Multi-source BFS	[ ]
7	All Paths from Source to Target	DFS backtracking	[ ]
8	Shortest Path in Binary Matrix	BFS	[ ]
9	Minimum Height Trees	BFS leaf trimming	[ ]