Graph Traversal Pattern

All lessons

Learn to treat grids, adjacency lists, and dependency chains as graphs — and how tracking visited nodes (not just recursing) is what separates this from Tree Traversal.

0/5 practice problems solved

Skip to practice

Recognizing the pattern

Reach for it when you need to

the input is a grid, adjacency list/matrix, or "connections between items" — cells/nodes can have more than one parent, or cycles;
you need to find connected components, shortest hops, or reachability;
the problem says "can you finish all tasks" or "is there a valid order" — that's often cycle detection via graph traversal (topological sort);
a grid problem asks about regions, flood fill, or spreading (islands, rotting oranges, water flow).

Don't use it when

The structure is guaranteed acyclic with exactly one parent per node — that's a tree, and Tree Traversal's simpler recursion applies without needing a visited set.
You just need aggregate stats over a flat sequence with no adjacency relationship.
The graph is dense and you need all-pairs shortest paths — that's typically a different algorithm (Floyd-Warshall) rather than a single BFS/DFS.

Core mental model

A graph traversal is BFS or DFS from Tree Traversal, plus one non-negotiable addition: a visited set, because a node can be reached more than one way. BFS still answers "fewest steps" questions (shortest path in an unweighted graph, rotting-oranges style spread). DFS still answers "is there a path/cycle" questions and is naturally recursive for grids (checking the four neighbors). The invariant is: never re-process a node once it's marked visited, and mark it visited at the moment you enqueue/recurse into it, not when you finish it — otherwise the same node can be queued twice.

Typical time: O(V + E)

Typical space: O(V)

Grid version: O(rows × cols)

Visual trace

BFS over a small 4-node cycle graph (1—2—3—4—1), starting from node 1. Visited tracking is what prevents revisiting 1 through the other path.

Visit 1, enqueue 2 and 4 — Start BFS at node 1. Mark it visited immediately and enqueue both unvisited neighbors.

Visit 2 and 4, enqueue 3 once — Both 2 and 4 see node 3 as a neighbor, but it's only enqueued the first time — the visited check stops the duplicate.

Scroll the diagrams sideways to see all of them.

Worked example: Clone Graph (BFS from node 1 on a 4-node cycle)

Graph edges: 1-2, 2-3, 3-4, 4-1. BFS from node 1, marking visited at enqueue time.

Step-by-step trace of Clone Graph (BFS from node 1 on a 4-node cycle)
Dequeue	Neighbors	Newly enqueued	Visited set
1	2, 4	2, 4	{1, 2, 4}
Key step: 2	1, 3	3	{1, 2, 3, 4}
4	3, 1	(none — 3 already visited)	{1, 2, 3, 4}

Invariant: A node is marked visited the moment it's enqueued, never later — otherwise it can be added to the queue twice before it's dequeued once.

Reusable template

The shape to adapt for a new problem in this pattern.

python

from collections import deque

def bfs(start, adjacency):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adjacency[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Common mistakes

Marking a node visited when it's dequeued instead of when it's enqueued, which lets it enter the queue multiple times.
Forgetting a visited set entirely (works fine on a tree, infinite-loops or double-counts on a graph with cycles).
On grid problems, not bounds-checking neighbor indices before looking them up, causing an out-of-range access.
Using DFS recursion on a huge grid without considering stack depth, or not converting to an iterative stack when needed.
For "can you finish all tasks" problems, doing a traversal without detecting back-edges/cycles — reachability alone isn't enough; you need cycle detection.

Practice: easy → medium → timed check

Solve in order; each step adds one decision to the same pattern.

1. Number of Islands
Medium
Not solved yet
Flood fill a grid as an implicit graph
Solution for Number of Islands Practice Number of Islands
2. Clone Graph
Medium
Not solved yet
BFS/DFS while building a parallel structure
Solution for Clone Graph Practice Clone Graph
3. Course Schedule
Medium
Not solved yet
Cycle detection via traversal
Solution for Course Schedule Practice Course Schedule
4. Pacific Atlantic Water Flow
Medium
Not solved yet
Multi-source traversal from two boundaries
Solution for Pacific Atlantic Water Flow Practice Pacific Atlantic Water Flow
5. Word Ladder
Hard
Not solved yet
BFS shortest path on an implicit graph
Solution for Word Ladder Practice Word Ladder

Final timed check

Run a 30-minute mock covering this pattern; state the invariant before coding, then finish with complexity and edge cases.

Start timed mock

Next lesson

System Design Interview Framework

Continue