Traversal

Representation covers how a graph is stored. This page covers how you walk one: the single engine behind BFS and DFS, why each behaves the way it does, and the handful of traps that come from getting the mechanics slightly wrong. Cycles & Ordering picks up from here - cycle detection, topological sort, and union-find are all DFS with one more idea layered on top.

1. One engine, two knobs

Every traversal you will ever write - tree, graph, grid, matrix - is the same loop wearing a different neighbour function. Nothing about "how do I visit everything reachable from here" changes between them. What changes is exactly two things:

1. the neighbour function - how you find who's adjacent to the node you're standing on
2. whether you need visited, and how you represent it - trees never revisit a node (no cycles), everything else does

Structure	Neighbours	Visited?
Tree	node.left, node.right	not needed (acyclic)
Graph	adj[node]	set()
Grid	4 directions + bounds check	mark cell in place
Matrix	j where M[i][j] == 1 (read column indices, not row values)	set()

A grid is just an implicit graph.

You never build an adjacency list - you compute neighbours on the fly from (r±1, c) and (r, c±1) with a bounds check. Recognising "grid = implicit graph" is what lets you reuse the exact same DFS/BFS you already wrote.

Once you can name both knobs for a given problem, you're not choosing between "the grid algorithm" and "the graph algorithm" - you're plugging two small answers into one loop. The rest of this page is that loop, twice: once run breadth-first with a queue, once run depth-first with a stack (or recursion, which is a stack, just one the language holds for you).

Which one a problem wants is almost always decided by what it asks for, not by the graph. The two jobs lists barely overlap:

DFS is the engine for	BFS is the engine for
Cycle detection - the recursion stack is the "am I on my own path" record (Cycles & Ordering)	Shortest path in an unweighted graph - fewest edges, which section 3 proves comes free with a queue
Topological sorting via postorder - a vertex finishes only after everything it depends on	Level-order / "how many rounds" - each queue drain is exactly one level, which is what makes multi-source BFS and rotting-oranges-style problems work
Strongly connected components - both Tarjan and Kosaraju are DFS with bookkeeping (MST & SCC)	Web crawling / broadcast - explore nearby before distant, and bound the work by depth
Path enumeration and backtracking - puzzles, mazes, "all paths from source to target"	Bipartite checking - alternate colours ring by ring (the 2-coloring check)
Connected components / flood fill - section 7 below (BFS works here too; DFS is just shorter to write)	*Anything asking for a minimum number of steps* - the word "minimum" plus unweighted edges is the BFS tell

⚠

DFS and BFS answer different questions

DFS cannot answer "shortest" and BFS cannot answer "does a path with property X exist." DFS reaches the target down whatever branch it happened to pick first, which may be arbitrarily long - there is no early exit that is safe. BFS has no notion of "the path I am currently on," so it cannot backtrack or undo a choice. Picking the wrong one is not a performance mistake, it is a wrong-answer mistake.

2. BFS: the algorithm

BFS explores in rings: everything at distance 1 from the start, then everything at distance 2, then distance 3, and so on - never touching a farther ring before every node in the current one has been visited. A FIFO queue is what makes this happen for free: you enqueue neighbours in the order you discover them, so the queue naturally drains ring 0 before ring 1 gets a chance to add anything of its own.

from collections import deque

 

def bfs(graph, start):

order, q = [], deque([start])

visited = {start} # marked at enqueue time

while q:

node = q.popleft()

for nb in graph[node]:

if nb not in visited:

visited.add(nb) # <-- mark HERE, the instant it enters the queue

q.append(nb)

order.append(node)

return order

The one detail that decides whether this is correct or merely "usually works": mark a node visited the instant it is enqueued, not when it is dequeued.

⚠

Mark visited on dequeue, not enqueue

Mark visited on dequeue and the same node gets enqueued multiple times before it's ever processed. Diamond graph A-B, A-C, B-D, C-D: B and C both enqueue D before D is dequeued, so D lands in the queue twice. It still terminates (a skip-guard on dequeue saves correctness) but it floods the queue with duplicates. Mark-on-enqueue makes each node enter the queue exactly once.

3. Why BFS's first arrival is always shortest

It is not enough to say "FIFO" - that just restates what a queue is. And "the first time we reach the target it must be shortest" is circular (it assumes the very thing to prove). The real reason is the monotone-queue invariant:

The queue holds at most two rings: distance d and distance d+1, in that order.

A ring-(d+1) node is only ever let into line by a ring-d node, so nothing farther away can jump the line.

Concretely, snapshot the queue's distances as you pop on A-B, A-C, B-D, C-D, D-E:

pop	distances in queue
A(0)	1
B(1)	2
C(1)	2
D(2)	3

E(3) can't enter the queue until D(2) is dequeued; for a 4 to sit in the queue a 3 must already be out; for a 3 to be out all 2s must be gone. So a node's first arrival is along a shortest path, and BFS can stop the instant it pops the target.

(Weighted edges break this - equal-hop no longer means equal-cost. That's what Dijkstra is for.)

4. DFS: recursive

Where BFS spreads outward ring by ring, DFS commits to one neighbour and plunges as deep as it can before backing up. The recursive call stack is the "how do I get back" mechanism - you never manage it yourself, which is exactly why the recursive version reads shorter than the iterative one below.

def dfs_recursive(graph, start):

order, visited = [start], {start}

def dfs(node):

for nb in graph[node]:

if nb not in visited:

visited.add(nb) # mark BEFORE the recursive call

order.append(nb)

dfs(nb)

dfs(start)

return order

The recursive twin of BFS's mark-on-enqueue rule: mark a node visited before you recurse into it, not after.

⚠

Marking after the recursive call causes infinite recursion

Mark after the recursive call and you get infinite recursion. On LeetCode 733 (Flood Fill), writing dfs(nr, nc) then grid[nr][nc] = new means the neighbour is never marked before you dive into it, so the two cells keep re-inviting each other - RecursionError on input as small as [[1,1,1]]. Mark before recurse is the recursive twin of mark-on-push.

Two more DFS facts worth keeping:

• No global/nonlocal needed here. The nested dfs only mutates order/visited (append/add), never rebinds them, so the closure shares them for free. global would just leak module names - a smell. (Contrast a running max like dia, which is reassigned and so needs nonlocal.)
• Recursive DFS dies past Python's ~1000-frame limit. A 2000-node chain (e.g. LC 207 with a long prerequisite chain) blows the stack. Iterative DFS doesn't.

5. DFS: iterative

Recursion is just a stack you can hold yourself, so an iterative DFS is a while loop over an explicit stack list instead of the call stack. The catch is that you now have to choose when a node gets marked, and there are exactly two valid choices - mixing them is the bug.

def dfs_iterative(graph, start):

order, stack, visited = [], [start], {start}

while stack:

node = stack.pop()

for nb in graph[node]:

if nb not in visited:

visited.add(nb) # mark-on-PUSH: each node enters the stack once, no dups

stack.append(nb)

order.append(node)

return order

• Mark-on-push (above): mark the instant you push. No duplicates ever sit on the stack.
• Mark-on-pop + skip-guard: push freely, mark when you pop, and if node in visited: continue at the top. This mirrors recursion and allows duplicates on the stack - the guard dedupes them when they re-pop. A grid flood-fill often uses this (if grid[r][c] == 0 is the dedupe guard).

⚠

Pop-guards don't replace marking visited

Don't mark-on-push but also keep a pop-guard like if grid[r][c] == 1 - that's a contradiction (you already marked it, so the guard is either dead code or fatally wrong).

6. BFS and DFS are one function apart

Put the two iterative loops side by side and the "single engine, two knobs" claim from section 1 stops being an analogy - it's the same function with one line swapped.

from collections import deque

 

def bfs(graph, start):

order, dq, visited = [], deque([start]), {start}

while dq:

node = dq.popleft() # <-- FIFO: oldest-discovered comes out first

for nb in graph[node]:

if nb not in visited:

visited.add(nb)

dq.append(nb)

order.append(node)

return order

 

def dfs_iterative(graph, start):

order, stack, visited = [], [start], {start}

while stack:

node = stack.pop() # <-- LIFO: most-recently-discovered comes out first

for nb in graph[node]:

if nb not in visited:

visited.add(nb)

stack.append(nb)

order.append(node)

return order

Everything else - the mark-on-push, the visited set, the shape of the loop - is identical. deque.popleft() vs list.pop() is the entire difference between "explore nearest first" and "explore deepest first." That single swap is why section 3's ring invariant holds for one and not the other: popleft always drains the oldest (shallowest) entries before the newest (deepest) ones ever get a turn, while pop does the opposite.

7. Connected components

A single DFS or BFS call only reaches what's reachable from its start node - on a disconnected graph, that's not everything. Counting components means running the traversal once per "island" of mutually-reachable nodes, which needs two loops with two different jobs.

Islands in an ocean.

Each maximal group of mutually-reachable nodes is one island. You need two loops - and confusing their jobs is the classic bug.

def count_components(graph):

visited, count = set(), 0

for node in graph: # OUTER: find fresh dry land

if node not in visited:

count += 1 # a brand-new island

dfs(node, graph, visited) # INNER: flood this entire island

return count

⚠

The outer-loop guard handles disconnected graphs

The outer-loop guard if node not in visited is what makes traversal work on disconnected graphs - it's the same guard connected components, cycle detection, and topological sort all share. Drop it and you either re-flood islands you've already counted, or (in cycle detection) call DFS on a finished node and get a false positive.

8. BFS variants worth knowing by name

Section 3's invariant - the queue only ever holds two adjacent distance rings - is what every variant below preserves. Each one is a small change to what goes into the queue at the start, or which end it goes into, and nothing else.

Multi-source BFS

Put every source into the queue before the loop, all at distance 0. The rings then expand from all of them simultaneously, and each vertex's distance comes out as the distance to its nearest source - not to a particular one.

from collections import deque

 

def multi_source_bfs(graph, sources):

dist = {s: 0 for s in sources}

q = deque(sources) # ALL sources seeded at distance 0

while q:

u = q.popleft()

for v in graph[u]:

if v not in dist:

dist[v] = dist[u] + 1

q.append(v)

return dist

⚠

Multi-source BFS gives distance, not source identity

Multi-source BFS gives you the distance, not the identity of the winning source. If you also need "which source is nearest," carry it in the queue entry or a second dict - you cannot recover it afterwards from dist alone. And seeding sources one at a time inside the loop instead of all before it breaks the ring invariant outright: a source added at step 5 is at distance 0 but sits behind vertices at distance 2.

0-1 BFS: a deque instead of a heap

When every edge weight is either 0 or 1, Dijkstra's heap is overkill. Use a deque: push a 0-weight neighbour on the front (same ring - it costs nothing to get there) and a 1-weight neighbour on the back (next ring). The two-ring invariant survives exactly, so the first settled distance is still optimal - at O(V + E) rather than O(E log V).

from collections import deque

 

def zero_one_bfs(graph, start, num_nodes):

# graph[u] = list of (v, weight) with weight in {0, 1}

INF = float('inf')

dist = [INF] * num_nodes

dist[start] = 0

dq = deque([start])

while dq:

u = dq.popleft()

for v, w in graph[u]:

if dist[u] + w < dist[v]:

dist[v] = dist[u] + w

if w == 0:

dq.appendleft(v) # same ring -> front of the line

else:

dq.append(v) # next ring -> back of the line

return dist

⚠

0-1 BFS must re-check dist on pop

0-1 BFS must re-check dist on pop, or accept duplicates - it cannot mark-on-enqueue. A vertex can legitimately enter the deque more than once, because a later 0-weight route may beat the 1-weight route that first found it. That is why the guard is a distance comparison rather than a visited set, and why this is the one BFS variant where mark-on-enqueue is wrong. It is Dijkstra's stale-entry skip in disguise.

Bidirectional BFS

To find the distance between one specific pair, grow two frontiers - one from the start, one from the target - and stop when they touch. If the branching factor is b and the answer is d, one BFS explores about b^d vertices while two meeting in the middle explore about 2 * b^(d/2). On a big-branching graph that is the difference between feasible and not.

def bidirectional_bfs(graph, start, target):

if start == target:

return 0

front, back = {start}, {target}

seen, steps = {start, target}, 0

while front and back:

if len(front) > len(back):

front, back = back, front # always expand the SMALLER frontier

steps += 1

nxt = set()

for u in front:

for v in graph[u]:

if v in back:

return steps # the frontiers met

if v not in seen:

seen.add(v)

nxt.add(v)

front = nxt

return -1

⚠

Bidirectional BFS only reports the distance reliably

Bidirectional BFS only works when the graph is traversable backwards, and only reliably reports the distance. On a directed graph the backward frontier must walk the reverse graph (Representation), not the forward one. Reconstructing the path needs a parent map on each side, spliced at the meeting vertex - and the two halves are built in opposite directions, so one must be reversed. It is also not worth it unless the frontier really does explode: on a sparse graph the bookkeeping costs more than it saves.

9. Implicit graphs: when there is no adjacency list

The most commonly missed graph problems are the ones that never mention a graph. A grid is the familiar case, but the general pattern is broader: any time a problem has states and legal moves between them, it is a graph, and "fewest moves" is BFS.

Problem shape	A vertex is	Neighbours are
Grid / maze / islands	a cell (r, c)	(r±1, c) and (r, c±1), filtered by bounds and walls
Word ladder (LC 127)	a word	every word one letter away that is in the dictionary
Open the lock (LC 752)	a 4-digit combination string	the 8 states one wheel-click away
Jump game / minimum jumps	an index	every index reachable in one jump
Sliding puzzle (LC 773)	the whole board, serialised to a string	the boards after each legal slide
Water jug / coin states	a tuple of amounts	the tuples after each legal pour or move
Knight moves on a board	a square	the 8 L-shaped destinations

The adjacency list is a function, not a data structure.

Nothing in BFS requires graph[u] to be a list you built - it only requires that you can produce u's neighbours when asked. Write that as a generator and the same BFS runs unchanged on a graph with 10^9 implicit vertices, because you only ever materialise the ones you actually reach.

from collections import deque

 

def bfs_implicit(start, is_target, neighbours):

seen = {start}

q = deque([(start, 0)])

while q:

state, d = q.popleft()

if is_target(state):

return d

for nxt in neighbours(state): # computed on demand, never stored

if nxt not in seen:

seen.add(nxt)

q.append((nxt, d + 1))

return -1

⚠

The seen set needs a hashable canonical key

The seen set must hold something hashable and canonical. A grid cell is fine as a tuple. A board or a multiset of amounts is not fine as a list, and is subtly wrong if two different serialisations describe the same state - you will re-explore states you have already handled, and on a large state space that is the difference between passing and timing out. Serialise deliberately: sort what is order-independent, and use tuple/str, never list/set.

⚠

Generating neighbours can dominate the runtime

Generating neighbours can dominate the runtime, and the fix is usually to invert the generator. Word ladder's naive neighbour function compares the current word against all n dictionary words at O(L) each - O(n * L) per vertex. Generating the L * 26 one-letter variants and testing set membership instead is O(L * 26) regardless of n. Same BFS, same answer; the neighbour function is where the complexity actually lives in an implicit graph.

Where to go next

The outer-loop guard in section 7 is the same guard cycle detection and topological sort both reuse - both are DFS with a bit more bookkeeping layered on top of exactly what you just read. Once edges stop costing the same, section 8's deque becomes a heap: that is Shortest Paths.