Graph Traversal
Explore nodes systematically using depth-first and breadth-first search patterns
Why Graph Traversal Is the Backbone of Algorithmic Problem Solving
Every time you ask Google Maps for the fastest route home, something remarkable happens beneath the surface. The app doesn't just guess β it traverses a massive graph of roads, intersections, and distances, systematically exploring paths until it finds the optimal one. You've already encountered this technology hundreds of times today without realizing it. Before you dive into free flashcards and code exercises in this lesson, ask yourself: what do GPS navigation, Facebook friend suggestions, package managers, and Google's search engine all have in common? The answer is graph traversal β and once you see it, you can't unsee it.
This lesson exists to give you that vision. Graph traversal is not just another algorithm topic to memorize for LeetCode. It is the lens through which an entire category of complex problems suddenly becomes solvable. By the end of this lesson, you'll recognize graph problems on sight, choose the right traversal strategy with confidence, and understand exactly why classic LeetCode problems like Number of Islands, Clone Graph, and Course Schedule all follow the same fundamental pattern.
Let's start by making the invisible visible.
The Hidden Graphs All Around You
Most programmers encounter graphs in textbooks as abstract node-and-edge diagrams, disconnected from anything that feels real. That abstraction is a mistake β and it's why so many developers freeze when they see a graph problem on a coding interview.
Here's the truth: graphs are the natural language of relationships. Anywhere two things connect, you have a graph waiting to be modeled. Let's walk through four domains where graph traversal does silent, essential work every single day.
π Social Networks
When LinkedIn suggests someone you might know, it's performing a traversal. Your profile is a node. Each connection you have is an edge to another node. "People you may know" are discovered by exploring nodes two or three edges away from you β a classic Breadth-First Search (BFS) pattern that fans outward level by level from a starting point.
Facebook's friend recommendation engine, Twitter's "who to follow" feature, and even Spotify's collaborative playlist suggestions all rely on this same traversal logic. The graph isn't metaphorical β it's literally stored as an adjacency structure in memory.
π‘ Real-World Example: When you search for "second-degree connections" on LinkedIn, the platform runs BFS starting from your node to depth 2, collecting every node reachable within two hops. That's exactly the algorithm you'll implement in this lesson.
πΊοΈ GPS Navigation
Your GPS models road networks as weighted graphs, where intersections are nodes and road segments are edges with weights representing distance or travel time. Finding the shortest path is a traversal problem β specifically, one that uses BFS-derived algorithms like Dijkstra's.
But even simpler problems, like "can I drive from city A to city B at all?", reduce to a connectivity check β the most fundamental graph traversal problem of all. If you can visit every node in a connected component starting from A, and B appears in that traversal, the path exists.
π¦ Dependency Resolution
Every time you run npm install or pip install, a package manager resolves dependency graphs. If package A depends on B, and B depends on C, the manager must install them in the right order. This is topological sorting β an algorithm built directly on top of Depth-First Search (DFS).
The LeetCode problem Course Schedule models exactly this: given a list of courses where some require prerequisites, can you complete all of them? It's a dependency graph. Detecting a cycle in that graph (which would make completion impossible) is pure DFS.
π·οΈ Web Crawling
Google's web crawler starts at a seed URL (a node), follows every hyperlink (an edge) to a new page (another node), and repeats. Without a visited set to track already-explored pages, the crawler would loop forever. This is graph traversal at planetary scale β billions of nodes, trillions of edges β but the core algorithm is identical to what you'll write in this lesson.
π€ Did you know? Google's original PageRank algorithm, which made it the world's dominant search engine, is fundamentally a graph traversal algorithm that ranks nodes by how many other high-value nodes point to them.
Why Graphs Are Different: The Problem with Linear Thinking
Before you can appreciate why graph traversal strategies exist, you need to understand why the approaches you use for arrays, linked lists, and trees fall short.
With a linear data structure like an array, traversal is simple: start at index 0, increment, stop at the end. With a tree, you have a root, parent-child relationships, and no cycles β a clean hierarchical flow. But graphs break both of these assumptions.
Linear (Array): Tree: Graph:
[A]-[B]-[C]-[D] A A --- B
|\ | / |
B C | / |
| C --- D
D |\n E (cycle back to A)
In a graph:
- Any node can connect to any other node β there's no guaranteed "start" or "end."
- Cycles can exist β without tracking visited nodes, you'll loop infinitely.
- Nodes can be unreachable β you may need to start traversal multiple times to cover the entire graph.
- Edges can be directed or undirected β the relationship may only flow one way.
This is why you need specialized traversal strategies. A naive "visit each element in order" approach simply doesn't work when the structure is non-linear and potentially cyclic.
π― Key Principle: The two fundamental challenges of graph traversal are avoiding infinite loops (solved with a visited set) and deciding the order in which to explore (solved by choosing BFS or DFS based on your goal).
The Two Primary Traversal Strategies: BFS and DFS
Every graph traversal algorithm you'll ever encounter on LeetCode descends from one of two foundational strategies. Understanding their core difference in philosophy is more important than memorizing their implementations β though you'll do both in this lesson.
Breadth-First Search (BFS): Explore Outward, Level by Level
Breadth-First Search starts at a source node and explores all of its immediate neighbors before moving to their neighbors. It's like dropping a stone in a pond and watching ripples expand outward in concentric rings.
BFS Exploration Order:
Start
A Level 0: [A]
/ \
B C Level 1: [B, C]
/ \ \
D E F Level 2: [D, E, F]
BFS uses a queue (first-in, first-out) to manage exploration. You enqueue the starting node, then repeatedly dequeue a node, process it, and enqueue all its unvisited neighbors.
BFS is ideal when:
- π― You need the shortest path between two nodes (in an unweighted graph)
- π― You're exploring by level or distance from a source
- π― You want to guarantee you find the closest solution first
Depth-First Search (DFS): Plunge Deep, Then Backtrack
Depth-First Search commits fully to one path until it hits a dead end, then backtracks and tries another. It's like exploring a maze by always turning left β going as deep as possible before reversing.
DFS Exploration Order (one possible path):
Start
A Visit: A
/ \
B C Visit: B (go deep left first)
/ \
D E Visit: D, backtrack, Visit: E,
backtrack to A, Visit: C
DFS uses a stack (or the call stack via recursion) to manage exploration. You push a node, process it, then push its unvisited neighbors, always diving into the most recently discovered node.
DFS is ideal when:
- π― You need to detect cycles in a graph
- π― You're doing topological sorting (ordering dependencies)
- π― You need to explore all possible paths or determine if a path exists
- π― You're working with problems that have a natural recursive structure
π‘ Mental Model: Think of BFS as a cautious explorer who maps every room on the first floor before going upstairs. DFS is an adventurous spelunker who descends as far as possible into one cave before climbing back up to try another.
π§ Mnemonic: BFS = Broad (wide exploration, uses a queue). DFS = Deep (deep exploration, uses a stack).
A First Look at the Code: Two Approaches to the Same Graph
To make BFS and DFS concrete from the start, let's look at both applied to the same simple graph. Don't worry about mastering every detail yet β Sections 3 and 4 will walk through each line carefully. This preview is about building intuition.
## Graph represented as an adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}
## BFS: Uses a queue, explores level by level
from collections import deque
def bfs(graph, start):
visited = set() # Track visited nodes to avoid loops
queue = deque([start]) # Initialize queue with starting node
visited.add(start)
order = []
while queue:
node = queue.popleft() # Dequeue from the FRONT
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) # Enqueue to the BACK
return order
print(bfs(graph, 'A')) # Output: ['A', 'B', 'C', 'D', 'E', 'F']
Notice how BFS visits A, then all of A's neighbors (B and C), then all of their neighbors (D, E, F). The queue ensures we fully process one level before descending.
## DFS: Uses recursion (implicit call stack), plunges deep first
def dfs(graph, start, visited=None, order=None):
if visited is None:
visited = set()
if order is None:
order = []
visited.add(start) # Mark current node as visited
order.append(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited, order) # Recurse deeper
return order
print(dfs(graph, 'A')) # Output: ['A', 'B', 'D', 'E', 'C', 'F']
DFS immediately commits to B after visiting A, then to D after visiting B. Only after exhausting B's branch does it backtrack to explore C. The call stack handles the "remember where I was" bookkeeping automatically.
β οΈ Common Mistake β Mistake 1: Forgetting to initialize the visited set before traversal begins. Without it, graphs with cycles cause infinite recursion or infinite loops. Always initialize visited before your first traversal call.
## Without visited tracking β DANGEROUS on cyclic graphs
graph_with_cycle = {
'A': ['B'],
'B': ['C'],
'C': ['A'] # Cycle back to A!
}
## β Wrong thinking: Just visit neighbors without tracking
def dfs_broken(graph, node):
for neighbor in graph[node]:
dfs_broken(graph, neighbor) # Will recurse forever!
## β
Correct thinking: Always maintain a visited set
def dfs_safe(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited: # Only visit unvisited nodes
dfs_safe(graph, neighbor, visited)
How This Lesson Connects to Real LeetCode Problems
Everything in this lesson is engineered around making you dangerous on LeetCode graph problems. Let's preview exactly how the concepts you're building map to problems you'll encounter.
π Quick Reference Card: Graph Traversal β LeetCode Problems
| LeetCode Problem | Core Traversal | What You'll Apply |
|---|---|---|
| π Number of Islands | DFS or BFS | Flood-fill connected components |
| π Clone Graph | DFS + HashMap | Deep copy with cycle-safe traversal |
| π Course Schedule | DFS | Cycle detection in directed graph |
| π’ Word Ladder | BFS | Shortest transformation path |
| πΊοΈ Rotting Oranges | BFS (multi-source) | Level-by-level spread simulation |
| π Path Exists in Graph | BFS or DFS | Basic connectivity check |
Let's make these concrete with a quick example. Number of Islands (LeetCode 200) gives you a 2D grid of '1's (land) and '0's (water). You need to count distinct islands.
How is this a graph problem? Each land cell is a node. Adjacent land cells share an edge. An island is a connected component β a group of nodes reachable from each other. Your task is to count connected components. That's it. Once you see the graph structure, the algorithm writes itself: iterate over every cell, and whenever you find an unvisited land cell, run DFS to mark the entire connected island as visited, then increment your counter.
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
island_count = 0
def dfs(r, c):
# Base cases: out of bounds, water cell, or already visited
if (r < 0 or r >= rows or
c < 0 or c >= cols or
grid[r][c] == '0' or
(r, c) in visited):
return
visited.add((r, c)) # Mark this cell as part of current island
# Explore all 4 adjacent directions
dfs(r + 1, c) # Down
dfs(r - 1, c) # Up
dfs(r, c + 1) # Right
dfs(r, c - 1) # Left
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r, c) not in visited:
dfs(r, c) # Traverse the entire island
island_count += 1 # Count it once DFS completes
return island_count
This solution follows the exact same DFS template you saw earlier. The graph is implicit (defined by adjacency in the grid rather than an explicit adjacency list), but the traversal logic is identical.
π‘ Pro Tip: Most LeetCode graph problems don't give you an explicit graph. You'll receive a grid, a matrix, or a list of edges and you'll need to recognize the underlying graph structure. This pattern recognition skill is what separates developers who struggle with graph problems from those who solve them confidently.
What LeetCode Graph Problems Have in Common
After solving hundreds of graph problems, experienced engineers notice that they almost all reduce to a small set of traversal patterns. Recognizing these patterns early is the single biggest accelerator for your graph problem-solving ability.
Here are the patterns you'll see repeatedly:
- π§ Connected Components: Count or analyze distinct groups of connected nodes (Number of Islands, Friend Circles)
- π§ Shortest Path: Find the minimum steps between two nodes (Word Ladder, Shortest Path in Binary Matrix)
- π§ Cycle Detection: Determine if a path exists that loops back to itself (Course Schedule, Detect Cycle in Graph)
- π§ Topological Sort: Order nodes such that all dependencies come first (Course Schedule II, Alien Dictionary)
- π§ Graph Coloring / Bipartiteness: Assign properties to nodes while maintaining constraints (Is Graph Bipartite?)
- π§ Multi-Source Traversal: Start BFS from multiple nodes simultaneously (Rotting Oranges, 01 Matrix)
Each of these patterns has a recognizable setup and a near-identical implementation across different problems. Once you internalize them β which is exactly what Sections 3 through 5 of this lesson will help you do β you'll approach any new graph problem by asking: which pattern does this match? rather than starting from scratch.
π― Key Principle: Pattern recognition beats memorization. You don't need to memorize solutions to 200 graph problems. You need to deeply understand 6-8 traversal patterns, and you'll be able to adapt them to any problem the interviewer presents.
What You'll Build in This Lesson
Here's exactly what lies ahead and why each section matters:
π Section 2 β Graph Fundamentals: You'll learn how graphs are represented in code (adjacency lists vs. adjacency matrices), the vocabulary you need (directed, undirected, weighted, cyclic), and how to read a problem and decide which representation to use.
π Section 3 β DFS Deep Dive: You'll master DFS with both recursive and iterative implementations, build strong mental models for when to use it, and trace through examples step by step.
π Section 4 β BFS Deep Dive: You'll build a parallel understanding of BFS, see its queue mechanics in detail, and learn why it's the go-to choice for shortest-path problems.
π Section 5 β Pitfalls and Best Practices: You'll see the most common mistakes (missing visited sets, wrong graph directions, off-by-one errors on grids) and learn defensive coding habits that prevent them.
π Section 6 β Cheat Sheet: Everything consolidated into quick-reference frameworks you can use while solving problems.
The journey from "I freeze when I see graph problems" to "I know exactly which pattern applies here" begins with understanding the why before the how. You've just completed that foundation.
π‘ Remember: Every GPS app, every social network, every package manager, every web crawler β they all rely on the algorithms you're about to master. This isn't abstract computer science. This is the technology you use every single day, and now you're going to understand how it actually works.
Let's build your graph traversal toolkit β starting with the vocabulary and representations that make everything else possible.
Graph Fundamentals: Representations and Terminology
Before you can write a single line of traversal code, you need a shared language for talking about graphs and a clear mental model of how they live in memory. This section builds that foundation. Think of it as stocking your toolbox β every term, every representation, every complexity trade-off you learn here will be reached for again and again across hundreds of problems. Skipping this groundwork is one of the most common reasons developers stall on graph problems despite understanding BFS and DFS in isolation.
The Core Vocabulary of Graphs
A graph is a structure made of two things: a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. That's it. Virtually everything else about graphs is a variation on that simple idea.
Let's build up the vocabulary with a concrete example. Imagine a network of five cities connected by roads:
A --- B
| / |
| / |
| / |
C --- D
\
E
Here, A, B, C, D, and E are vertices (V = 5). The lines between them are edges (E = 6). Notice two things about this picture: you can travel in either direction along each road, and no road has a toll attached to it. Those two observations introduce the first set of important distinctions.
Directed vs. Undirected Graphs
In an undirected graph, every edge is a two-way street. If there is an edge between A and B, you can travel from A to B and from B to A. Most "friendship" or "connection" style problems (social networks, road maps between cities) are undirected.
In a directed graph (also called a digraph), every edge has a direction β an arrow pointing from a source vertex to a destination vertex. If there is a directed edge from A to B, you can travel A β B, but not necessarily B β A. Task scheduling, web page link following, and dependency resolution are classic directed graph problems.
Undirected: Directed:
A --- B A ---> B
| | | ^
C --- D v |
C ---> D
Weighted vs. Unweighted Graphs
An unweighted graph treats all edges as equal β traversing any edge costs the same. A weighted graph assigns a numerical weight (or cost) to each edge. Road networks with distances, flight routes with prices, and networks with bandwidth limits are all weighted graphs. For this lesson, we focus on traversal of unweighted graphs, but understanding the distinction matters because BFS's "shortest path" guarantee only holds in unweighted graphs.
Cyclic vs. Acyclic Graphs
A cycle exists when you can start at a vertex, follow edges, and return to the same vertex without retracing any edge. A graph containing at least one cycle is cyclic. A graph with no cycles is acyclic. A DAG (Directed Acyclic Graph) is a directed graph with no cycles β it comes up constantly in problems about scheduling, dependency ordering, and topological sort.
π― Key Principle: Detecting whether a graph is cyclic is itself a graph traversal problem. The moment you know a graph might have cycles, your traversal algorithm needs a "visited" mechanism to avoid infinite loops.
Degree and Connectivity
The degree of a vertex is the number of edges connected to it. In directed graphs, you distinguish in-degree (edges arriving) from out-degree (edges leaving). A graph is connected if there is a path between every pair of vertices. In directed graphs, the stronger concept is strongly connected, meaning every vertex can reach every other vertex by following directed edges.
π§ Mnemonic: Think Vertices as Villages and Edges as roads between them. The graph vocabulary then becomes intuitive β connected means you can drive from any village to any other, directed means some roads are one-way, and weighted means roads have different travel times.
Adjacency List Representation
Now that we have vocabulary, we need to talk about how graphs are actually stored in code. The dominant choice for LeetCode problems β and for most real-world applications β is the adjacency list.
In an adjacency list, each vertex maintains a list of its neighbors (the vertices it shares an edge with). You can implement this with a dictionary (hash map) mapping each vertex to a list of its neighbors, or with an array of lists when vertices are numbered.
## Building an adjacency list from an edge list
## Edges given as pairs: [[0,1],[0,2],[1,3],[2,3],[3,4]]
from collections import defaultdict
def build_adjacency_list(n, edges, directed=False):
"""
n: number of vertices (labeled 0 to n-1)
edges: list of [u, v] pairs
directed: if False, add edges in both directions
"""
graph = defaultdict(list) # Each key maps to a list of neighbors
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u) # Undirected: add the reverse edge too
return graph
## Example usage
edges = [[0,1],[0,2],[1,3],[2,3],[3,4]]
graph = build_adjacency_list(5, edges)
## Result:
## graph[0] = [1, 2]
## graph[1] = [0, 3]
## graph[2] = [0, 3]
## graph[3] = [1, 2, 4]
## graph[4] = [3]
Let's visualize what this looks like in memory:
Vertex Neighbors
0 -> [1, 2]
1 -> [0, 3]
2 -> [0, 3]
3 -> [1, 2, 4]
4 -> [3]
Why Adjacency Lists Win for Most LeetCode Problems
The adjacency list shines because of how it handles sparse graphs β graphs where the number of edges is much smaller than the theoretical maximum. Most real-world graphs (and most LeetCode graphs) are sparse. In a sparse graph, adjacency lists use only the space you actually need: O(V + E) total space, where V is the number of vertices and E is the number of edges.
Equally important: when you traverse a graph, you iterate over a vertex's neighbors. With an adjacency list, that operation takes time proportional to the actual number of neighbors of that vertex, not the total number of vertices in the graph.
π‘ Pro Tip: When a LeetCode problem gives you n nodes and a list of edges, your first step should almost always be to convert that edge list into an adjacency list. This single transformation makes traversal code clean, fast, and easy to reason about.
Adjacency Matrix Representation
The alternative is the adjacency matrix: a 2D grid of size V Γ V where matrix[i][j] = 1 (or the edge weight) if an edge exists from vertex i to vertex j, and 0 otherwise.
## Building an adjacency matrix
def build_adjacency_matrix(n, edges, directed=False):
"""
n: number of vertices
edges: list of [u, v] pairs
"""
# Initialize V x V grid with zeros
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
if not directed:
matrix[v][u] = 1 # Undirected: mark both directions
return matrix
## For our 5-vertex example:
## matrix[0][1] = 1, matrix[0][2] = 1
## matrix[1][0] = 1, matrix[1][3] = 1
## ... and so on
## Checking if edge (2, 3) exists: O(1) lookup
edges_exist = matrix[2][3] # Returns 1
The adjacency matrix looks like this for our example (rows and columns are vertices 0β4):
0 1 2 3 4
0 [ 0 1 1 0 0 ]
1 [ 1 0 0 1 0 ]
2 [ 1 0 0 1 0 ]
3 [ 0 1 1 0 1 ]
4 [ 0 0 0 1 0 ]
Trade-offs: When to Use Which
π Quick Reference Card:
| π§ Adjacency List | π Adjacency Matrix | |
|---|---|---|
| π¦ Space | O(V + E) | O(VΒ²) |
| π Check if edge (u,v) exists | O(degree of u) | O(1) |
| π Iterate all neighbors of u | O(degree of u) | O(V) |
| β Best for | Sparse graphs, traversal | Dense graphs, edge lookups |
| β οΈ Watch out | Slightly more setup code | Blows up on large V |
β οΈ Common Mistake: Mistake 1: Defaulting to an adjacency matrix because it "feels simpler." If V = 100,000 (a common LeetCode scale), an adjacency matrix would require 100,000 Γ 100,000 = 10 billion cells β completely infeasible. Adjacency lists handle this trivially as long as the number of edges stays manageable. β οΈ
The adjacency matrix earns its place when you need O(1) edge existence checks and the graph is dense (E is close to VΒ²). Floyd-Warshall shortest paths and some dynamic programming on graphs use matrices naturally. But for traversal problems β the focus of this lesson β the adjacency list is almost always the right tool.
Implicit Graphs: The Hidden Graph Problems
One of the most important skills in graph problem solving is recognizing when a problem is a graph problem even when no graph is explicitly given. These are called implicit graphs, and they appear constantly on LeetCode.
Grids as Graphs
The most common implicit graph is a 2D grid. Consider a matrix where each cell can be land or water. The question "how many islands are there?" is really asking: how many connected components exist in a graph where each land cell is a vertex and edges connect horizontally and vertically adjacent land cells?
Grid: Implicit Graph (land cells only):
1 1 0 0 (0,0)-(0,1)
1 0 0 1 |
0 0 0 1 (1,0) (1,3)-(2,3)
0 0 0 1
When you traverse this grid with DFS or BFS, you're performing graph traversal β you just never explicitly built an adjacency list. Instead, you compute neighbors on the fly: for cell (r, c), the neighbors are (r+1,c), (r-1,c), (r,c+1), (r,c-1) β subject to boundary checks.
π‘ Mental Model: A grid of size M Γ N is a graph with M Γ N vertices and up to 2ΓMΓN edges (each cell connects to at most 4 neighbors, but each edge is shared, so roughly 2MN edges total). Every grid traversal problem is a graph problem in disguise.
Trees as Graphs
A tree is actually a special case of a graph: it is a connected, undirected, acyclic graph with exactly V β 1 edges. Binary trees and N-ary trees you've seen in earlier lessons are graphs. The difference is that trees have no cycles and have a designated root, which simplifies traversal (you never need a separate "visited" set because acyclicity prevents revisiting). When a LeetCode problem gives you a general graph that happens to be a tree (often stated as "there are n nodes and n-1 edges"), recognize that tree traversal techniques apply directly.
State Spaces as Graphs
Some of the trickiest implicit graphs involve abstract state spaces. In the classic "Word Ladder" problem, you transform one word into another by changing one letter at a time. Each word is a vertex; two words share an edge if they differ by exactly one letter. Finding the shortest transformation sequence is a shortest-path problem on this implicit graph β solved with BFS.
π€ Did you know? The number of "reachable states" in a state-space graph can be astronomically large, but BFS and DFS only visit states they can actually reach from the starting state. This is why implicit graphs are tractable even when the theoretical graph is enormous.
Recognizing Implicit Graph Problems
Here is a reliable pattern for spotting implicit graphs:
- π§ "Find connected components" β graph with DFS/BFS
- π "Shortest path from X to Y" on a grid or in a state space β BFS on implicit graph
- π§ "Can we reach Y from X?" β reachability on implicit graph
- π― "Minimum steps / moves" in a game, puzzle, or grid β BFS on state-space graph
- π "Number of islands / regions / groups" β connected components on grid graph
β Wrong thinking: "This is a grid problem, not a graph problem β I need a special grid algorithm." β Correct thinking: "This grid is an implicit graph. I'll apply standard BFS or DFS, computing neighbors on the fly instead of building an explicit adjacency list."
Time and Space Complexity Baselines
The most important complexity result for graph traversal is this: any complete traversal of a graph β visiting every vertex and exploring every edge β costs O(V + E) time and O(V) space (for the visited tracking structure).
Let's unpack what that means in practice.
What V and E Mean in Practice
V is the number of vertices. E is the number of edges. The sum V + E appears because traversal does two distinct kinds of work:
- Processing each vertex once: when a vertex is first discovered, you do O(1) work to mark it visited and add it to the frontier. This contributes O(V) total.
- Examining each edge once (or twice for undirected graphs): when processing a vertex, you look at all its neighbors. Across the entire traversal, every edge gets examined. This contributes O(E) total.
For an undirected graph, each edge (u, v) appears in both graph[u] and graph[v], so it gets examined twice β but O(2E) = O(E), so the asymptotic result is the same.
Traversal work breakdown:
Vertex processing: O(V) [mark each vertex visited once]
Edge examination: O(E) [scan each neighbor list fully]
-----------------------------------------
Total time: O(V + E)
Visited array/set: O(V) [one entry per vertex]
Traversal stack/queue: O(V) [at most V vertices in the frontier]
-----------------------------------------
Total space: O(V)
Interpreting V + E for Different Graph Types
The relationship between V and E varies by graph type, and understanding this helps you interpret complexity bounds intuitively:
- Sparse graph (like a tree): E β V, so O(V + E) β O(V). Traversal is fast.
- Dense graph: E β VΒ², so O(V + E) β O(VΒ²). Traversal still visits everything, but "everything" is a lot more.
- Grid of size M Γ N: V = M Γ N, E β 2 Γ M Γ N, so O(V + E) = O(M Γ N). The grid size directly determines traversal time β no surprises.
π‘ Real-World Example: LeetCode's "Number of Islands" (Problem 200) has a grid of up to 300 Γ 300 = 90,000 cells. Your traversal visits each cell at most once and examines each of the roughly 180,000 edges at most once. That's about 270,000 operations β well within any time limit. The O(V + E) analysis tells you immediately that a single traversal is efficient enough.
The Space Cost of Recursion
One subtlety: recursive DFS uses the call stack as implicit space. In the worst case (a path graph β a straight line of V vertices), the recursion depth reaches V, meaning O(V) stack frames. This is already accounted for in the O(V) space bound, but it's worth flagging because deep recursion can hit Python's default recursion limit (usually 1,000).
β οΈ Common Mistake: Mistake 2: Forgetting that recursive DFS on a graph with V = 10,000 nodes can trigger a RecursionError in Python. Either increase the recursion limit with sys.setrecursionlimit, or convert to iterative DFS using an explicit stack. We'll cover this in detail in the DFS section. β οΈ
Putting It All Together: A Mental Checklist
When you encounter a new graph problem on LeetCode, run through this checklist before writing any code:
- π§ Is the graph explicit or implicit? Did the problem give you an edge list, or is the graph hidden inside a grid, tree, or state space?
- π Is it directed or undirected? This determines whether you add reverse edges when building your adjacency list.
- π§ Is it weighted or unweighted? This determines whether BFS gives you shortest paths (unweighted only).
- π― Can it have cycles? If yes, your traversal needs a visited set. If no (e.g., it's a tree or DAG), you may be able to simplify.
- π How large are V and E? Estimate the traversal cost with O(V + E). If V β 10β΅ and E β 10β΅, you're looking at about 200,000 operations β fine. If E β VΒ², reconsider your approach.
With this checklist in hand and the vocabulary firmly in place, you're ready to write graph traversal code with clarity and confidence. In the next section, we'll build Depth-First Search from the ground up β armed with exactly the representation and complexity knowledge you now have.
Depth-First Search (DFS): Strategy, Implementation, and Intuition
Imagine you're exploring a sprawling cave system with a single torch. Your instinct is to pick one tunnel and go as deep as it takes β past forks, past chambers, all the way to the dead end β before you turn around and try the next unexplored branch. That instinct is Depth-First Search. It's one of the most elegant and powerful algorithms in computer science, and once you internalize its mechanics, you'll start recognizing its fingerprints in dozens of LeetCode problems that initially seem unrelated.
The Call-Stack Mental Model: Going Deep Before Going Wide
Depth-First Search (DFS) is a graph traversal strategy that explores a path as far as possible before backtracking to explore alternative paths. The word "depth" is the key: DFS commits to going down before it goes sideways.
The most intuitive way to understand DFS is through the call stack β the mechanism your program uses to track function calls. When DFS visits a node, it immediately recurses into that node's first unvisited neighbor. That call recurses again, and again, pushing frames onto the stack until there's nowhere left to go. Then the stack unwinds, popping back to the most recent fork in the road and trying the next option. This unwinding is backtracking.
Graph:
A
/ \
B C
/ \ \
D E F
DFS from A (visiting neighbors left-to-right):
Stack state over time:
[A] β visit A
[A, B] β visit B
[A, B, D] β visit D (dead end, backtrack)
[A, B] β back at B
[A, B, E] β visit E (dead end, backtrack)
[A] β back at A
[A, C] β visit C
[A, C, F] β visit F (dead end, backtrack)
[] β done
Visit order: A β B β D β E β C β F
π‘ Mental Model: Think of DFS as a commitment algorithm. Once it picks a direction, it goes all-in until it hits a wall, then reevaluates. BFS (covered next) is the opposite β it hedges its bets and explores all options at the current depth before going deeper.
This mental model matters practically because the call stack in recursive DFS and the explicit stack in iterative DFS are doing the same job: remembering where to backtrack to. Understanding that equivalence will make both implementations feel natural.
Recursive DFS Implementation
The recursive implementation is the clearest expression of DFS's logic. For a graph represented as an adjacency list (a dictionary mapping each node to its list of neighbors), the implementation almost writes itself:
def dfs_recursive(graph: dict, start: int) -> list:
"""
Performs DFS on a graph from a start node.
Returns the list of nodes in DFS visit order.
graph: adjacency list, e.g. {0: [1, 2], 1: [3], 2: [4], 3: [], 4: []}
start: the node to begin traversal from
"""
visited = set() # Tracks visited nodes to prevent revisiting
visit_order = [] # Records the order nodes are first visited
def dfs(node):
# Base case: if already visited, stop exploring this path
if node in visited:
return
# Mark as visited BEFORE recursing to handle cycles
visited.add(node)
visit_order.append(node) # Pre-order: process node on the way DOWN
# Recurse into each unvisited neighbor
for neighbor in graph[node]:
dfs(neighbor)
# Post-order processing would go here (on the way back UP)
# e.g., post_order.append(node)
dfs(start)
return visit_order
## Example usage:
graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [],
5: []
}
print(dfs_recursive(graph, 0)) # Output: [0, 1, 3, 4, 2, 5]
The single most important line in this implementation is visited.add(node) β and its placement matters enormously. You mark a node as visited before you recurse into its neighbors. This is the guard that prevents infinite loops on cyclic graphs.
β οΈ Common Mistake: Marking a node as visited after processing its neighbors instead of before. On a cyclic graph like 0 β 1 β 0, this causes infinite recursion. The visited set is your cycle-breaker, and it must be activated the moment you enter a node.
Cyclic graph without visited guard:
0 β 1 β 0 β 1 β 0 ... (infinite loop, stack overflow)
With visited guard:
Visit 0 β mark 0 visited β visit 1 β mark 1 visited
β try to visit 0 again β already in visited β stop β
π― Key Principle: The visited set serves a dual purpose β it prevents infinite loops on cyclic graphs and it prevents redundant work by ensuring each node is processed exactly once, giving DFS its O(V + E) time complexity where V is vertices and E is edges.
Iterative DFS Implementation
Recursion is elegant, but it has a hard limit: Python's default recursion depth is 1,000. On large graphs, a deeply nested recursive DFS will hit a RecursionError. The iterative version solves this by replacing the implicit call stack with an explicit stack β a plain Python list used in last-in, first-out (LIFO) fashion.
def dfs_iterative(graph: dict, start: int) -> list:
"""
Iterative DFS using an explicit stack.
Functionally equivalent to recursive DFS.
Key insight: the stack stores nodes we've DISCOVERED
but not yet fully processed β same role as the call stack.
"""
visited = set()
visit_order = []
stack = [start] # Initialize stack with the start node
while stack:
node = stack.pop() # LIFO: take the most recently added node
# Skip if already visited (possible with this approach)
if node in visited:
continue
visited.add(node)
visit_order.append(node)
# Push neighbors onto stack
# Note: pushing in reverse order preserves left-to-right visit order
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return visit_order
## Same graph as before:
graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [],
5: []
}
print(dfs_iterative(graph, 0)) # Output: [0, 1, 3, 4, 2, 5]
Notice the subtle difference in where the visited check occurs. In the recursive version, we check at the top of the function (once per call). In the iterative version, we check at the top of the loop, after popping β because a node can be pushed onto the stack multiple times (once by each of its neighbors) before it's ever visited. The continue guard handles duplicates cleanly.
π‘ Pro Tip: The reversed() call when pushing neighbors is a cosmetic choice β it makes the iterative version produce the same visit order as the recursive version (which naturally visits the first neighbor first). In interview settings, visit order often doesn't matter, so you can skip reversed() for cleaner code.
How Iterative Mirrors Recursive
The parallel between recursive and iterative DFS is worth making explicit:
| Recursive DFS | Iterative DFS |
|---|---|
| Call stack (managed by Python runtime) | Explicit stack (your list) |
| Function call pushes a frame | stack.append(neighbor) |
| Function return pops a frame | stack.pop() |
| Reaches base case, unwinds | Stack empties, loop ends |
visited set prevents re-entry |
visited set + continue guard |
π§ Mnemonic: "DFS = stack, BFS = queue." This single rule tells you which data structure to reach for when implementing either traversal iteratively. Deep (stack) vs. Broad (queue).
Pre-Order vs. Post-Order Processing
One of DFS's most powerful features β and most commonly overlooked β is when you process a node relative to its recursive calls. This timing splits DFS into two distinct flavors: pre-order and post-order processing.
Pre-order processing happens when you record or act on a node the moment you enter it β on the way down the recursion. This is what the examples above do with visit_order.append(node) placed before the recursive loop. It answers the question: "In what order did I discover these nodes?"
Post-order processing happens after all of a node's descendants have been fully explored β on the way back up through backtracking. To implement it, you simply move the processing logic to after the recursive loop:
def dfs_with_postorder(graph: dict, start: int):
"""
Demonstrates both pre-order and post-order processing.
Post-order is essential for problems like topological sort.
"""
visited = set()
pre_order = [] # Nodes in entry order (discovery order)
post_order = [] # Nodes in exit order (completion order)
def dfs(node):
if node in visited:
return
visited.add(node)
pre_order.append(node) # Pre-order: node is entered
for neighbor in graph[node]:
dfs(neighbor)
post_order.append(node) # Post-order: all descendants finished
dfs(start)
return pre_order, post_order
## DAG example (Directed Acyclic Graph):
## Task dependencies: C depends on A; D depends on B and C
graph = {
'A': ['C'],
'B': ['D'],
'C': ['D'],
'D': []
}
pre, post = dfs_with_postorder(graph, 'A')
print("Pre-order: ", pre) # ['A', 'C', 'D']
print("Post-order:", post) # ['D', 'C', 'A']
## Topological sort = reverse of post-order: ['A', 'C', 'D']
The practical implications of this distinction are significant:
π― Key Principle: Reversing the post-order list of a DFS on a DAG gives you a valid topological ordering. This is why post-order DFS is the engine inside Kahn's-alternative topological sort. Nodes that finish last (appear last in post-order) are the ones with no remaining dependencies β they belong at the start of the topological order.
DAG and post-order intuition:
A β C β D
B ------β
To complete D, you must first complete A, B, and C.
So D finishes LAST in post-order β it goes LAST in
the reversed list β in topological order, D appears
after all its prerequisites. β
π‘ Real-World Example: Build systems like make or package managers like npm use topological sort under the hood. When you run npm install, the dependency resolver is essentially running a post-order DFS on a directed dependency graph to determine the correct installation sequence.
Identifying DFS-Friendly Problem Patterns
Recognizing when to reach for DFS is as important as knowing how to implement it. Several recurring LeetCode problem shapes are essentially DFS problems in disguise.
Connected Components
A connected component is a maximal subgraph where every node is reachable from every other node. Counting connected components is a classic DFS application: you iterate over all nodes, and any time you find an unvisited node, you launch a DFS from it (marking everything it touches as visited). Each DFS launch corresponds to discovering a new component.
Graph with 3 connected components:
[0 - 1 - 2] [3 - 4] [5]
Algorithm:
- Visit 0 β DFS marks {0, 1, 2} β components = 1
- Visit 1 β already visited, skip
- Visit 2 β already visited, skip
- Visit 3 β DFS marks {3, 4} β components = 2
- Visit 4 β already visited, skip
- Visit 5 β DFS marks {5} β components = 3
π§ LeetCode Problems: Number of Islands (LC 200), Number of Connected Components in an Undirected Graph (LC 323), Max Area of Island (LC 695) β all reduce to counting or measuring DFS-reachable regions.
Path Existence
When a problem asks "does a path exist from node A to node B?", DFS is a natural fit. You launch from A and check whether B is ever marked visited by the time DFS completes. This is often simpler than BFS for path existence (though BFS is better for shortest path, as covered in the next section).
β Wrong thinking: "I need shortest path, so BFS; I need any path, so BFS too." β Correct thinking: "Shortest path β BFS. Any path / reachability β DFS is often simpler and sufficient."
Cycle Detection
DFS is the go-to tool for cycle detection. On a directed graph, a cycle exists if DFS ever encounters a node that is currently in the active recursion path (the call stack) β as opposed to a node that was visited in a previous DFS branch. This requires tracking a separate in_stack (or "grey") set alongside the visited set.
Cycle detection states:
WHITE (unvisited) β never seen
GREY (in-stack) β currently being explored
BLACK (visited) β fully processed, all descendants done
If DFS reaches a GREY node β cycle detected! β
If DFS reaches a BLACK node β no new cycle (already processed)
Topological Ordering Hints
Any problem involving ordering with dependencies is a topological sort problem, and DFS is one of the two standard algorithms for solving it. Look for phrases like:
- π― "Complete task X before task Y"
- π― "Module A depends on module B"
- π― "Find a valid build/install order"
- π― "Detect a circular dependency"
All of these map to a directed graph where you need to either (a) find a valid topological order or (b) detect that no valid order exists (i.e., a cycle is present). Post-order DFS handles both.
π Quick Reference Card:
| π― Problem Pattern | π§ DFS Technique | π Example LeetCode Problem |
|---|---|---|
| π Connected components | DFS flood-fill, count launches | LC 200: Number of Islands |
| π Path existence | DFS from source, check target | LC 547: Friend Circles |
| π Cycle detection | Track in-stack (grey) nodes | LC 207: Course Schedule |
| π Topological sort | Reverse post-order DFS | LC 210: Course Schedule II |
| π Tree traversals | Pre/in/post-order DFS | LC 94: Binary Tree Inorder |
| π Maze/grid search | DFS with (row, col) visited set | LC 79: Word Search |
Putting It All Together: The DFS Checklist
Before writing a single line of DFS code on a new problem, run through this mental checklist:
- π§ What is the graph? Explicit edges, or implicit (grid cells are nodes, adjacency is up/down/left/right)?
- π Is the graph directed or undirected? Directed graphs need care with cycle detection (grey/black distinction). Undirected graphs need to avoid revisiting the parent node.
- π§ Recursive or iterative? Recursive is cleaner for most interviews; iterative for large inputs at risk of stack overflow.
- π― Pre-order or post-order? Asking about discovery order? Pre-order. Asking about completion order or dependencies? Post-order.
- π What goes in the visited set? For grids, typically
(row, col)tuples. For general graphs, node identifiers.
β οΈ Common Mistake: On undirected graphs, forgetting to avoid traversing back to the parent. If node 1 connects to node 2 in an undirected graph, don't let the DFS from 2 immediately revisit 1 β your visited set handles this correctly, but if you're tracking the current path explicitly (e.g., for cycle detection), you need to also pass the parent node into the recursive call.
π€ Did you know? DFS was first formalized by mathematician Charles Pierre TrΓ©maux in the 19th century as a strategy for solving mazes β over a century before computers existed. His algorithm is essentially what we call DFS today, implemented by leaving and erasing marks on tunnel walls.
DFS is the algorithmic equivalent of committed, focused exploration. It goes deep, it backtracks gracefully, and it leaves no stone unturned. In the next section, you'll meet its complement β BFS β which trades that commitment for a guarantee: whatever it finds first, it finds fast.
Breadth-First Search (BFS): Strategy, Implementation, and Intuition
If DFS is the explorer who dives headlong into the unknown, Breadth-First Search is the methodical cartographer who maps every inch of the current territory before advancing a single step further. Where DFS charges down one path until it hits a dead end, BFS radiates outward in concentric rings, touching every neighbor at distance 1 before any neighbor at distance 2, every node at distance 2 before any at distance 3, and so on. This fundamental difference in exploration strategy makes BFS the indispensable tool whenever a problem cares not just about whether a path exists, but about how short that path is.
Understanding BFS deeply β not just memorizing its template β will unlock solutions to dozens of LeetCode problems that would otherwise seem intractable.
The Queue Mental Model: Exploring Layer by Layer
The engine driving BFS is the queue, a First-In-First-Out (FIFO) data structure. The queue is not just an implementation detail; it is the physical embodiment of BFS's exploration philosophy. When you enqueue a node's neighbors, you are promising: "I will visit all of you before I visit anyone you know." Because older entries are processed before newer ones, the traversal naturally fans out level by level.
Consider this simple graph:
A
/ \
B C
/ \ \
D E F
Starting from A, BFS explores in these waves:
Level 0: [A] β Process A, enqueue B, C
Level 1: [B, C] β Process B (enqueue D, E), Process C (enqueue F)
Level 2: [D, E, F] β Process D, E, F (no unvisited neighbors)
At no point does BFS descend to D before it has finished with C. This is the crucial guarantee: all nodes at depth k are visited before any node at depth k+1.
π‘ Mental Model: Imagine dropping a stone into still water. The ripples expand outward in perfect circles β each ring fully formed before the next begins. BFS is that stone's ripple. Each ring is one level of the graph.
π― Key Principle: The queue enforces BFS's level-by-level contract. A stack (used in DFS) breaks that contract because it prioritizes the most-recently-seen node, diving deep instead of spreading wide.
BFS Implementation in Python
The canonical BFS template in Python uses collections.deque rather than a plain list. This is not arbitrary β deque supports O(1) pops from the left (popleft()), whereas list.pop(0) requires O(n) time because every element must shift. On large graphs, this difference is the distinction between an accepted solution and a Time Limit Exceeded verdict.
Here is the foundational BFS template, annotated line by line:
from collections import deque
def bfs(graph: dict, start: str) -> list:
"""
Perform BFS traversal of an adjacency-list graph.
Returns nodes in the order they were visited.
"""
visited = set() # Track visited nodes to avoid revisiting
queue = deque() # Our FIFO frontier
# β
Critical: mark visited BEFORE enqueuing, not after dequeuing
visited.add(start)
queue.append(start)
visit_order = []
while queue:
node = queue.popleft() # O(1) removal from the left
visit_order.append(node) # Process the current node
for neighbor in graph[node]: # Examine all neighbors
if neighbor not in visited:
visited.add(neighbor) # Mark visited immediately
queue.append(neighbor) # Schedule for future processing
return visit_order
## Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']
β οΈ Common Mistake β Marking Visited at Dequeue Time: One of the most frequent BFS bugs is adding a node to visited only when you pop it from the queue, rather than when you push it. Here is why this is dangerous:
β Wrong thinking: "I'll mark it visited when I actually process it."
β
Correct thinking: "I mark it visited the moment I decide to enqueue it."
If you wait until dequeue time, the same node can be enqueued multiple times by different neighbors before you ever process it. In a dense graph, this can cause exponential duplicate work β or worse, an infinite loop in graphs with cycles. Always mark a node visited before enqueuing it.
Why BFS Guarantees the Shortest Path
This is one of the most important theoretical guarantees in all of graph algorithms, and it falls directly from the queue's FIFO behavior.
Claim: In an unweighted graph, the first time BFS reaches any node v from source s, the path taken is the shortest possible path from s to v.
Intuition: BFS explores nodes in non-decreasing order of their distance from the source. Nodes at distance 1 are processed before nodes at distance 2, which are processed before nodes at distance 3, and so on. Therefore, the very first time a node enters the queue, it has been reached via the fewest possible hops.
Contrast this with DFS. DFS might reach node F via the path A β B β D β E β F (length 4) even if the path A β C β F (length 2) exists. DFS has no mechanism for preferring shorter paths β it simply follows wherever the current branch leads.
Graph: BFS from A finds F via: DFS from A might find F via:
A A β C β F (β
shortest) A β B β D β E β F (β longer)
/ \
B C
| \
D F
|
E
π― Key Principle: BFS = shortest path in unweighted graphs. For weighted graphs, you need Dijkstra's algorithm, which generalizes BFS by replacing the queue with a priority queue sorted by cumulative edge weight.
π€ Did you know? BFS is the foundational idea behind more advanced algorithms like Dijkstra, 0-1 BFS (for graphs with only 0 or 1 weight edges), and even bidirectional BFS β where you run two simultaneous BFS traversals from source and target and stop when they meet in the middle, dramatically reducing search space.
Level-Tracking: Knowing Which Wave You're On
Many LeetCode problems don't just ask if you can reach a node β they ask how many steps it takes, or they ask you to process nodes level by level (e.g., binary tree level-order traversal, minimum steps in a maze, or word ladder transformations). For these, you need the level-tracking technique.
There are two clean approaches.
Approach 1: Queue Sentinel / Size Snapshot
At the start of each level, record the current size of the queue. Process exactly that many nodes β they all belong to the current level. Any nodes added during this processing belong to the next level.
from collections import deque
def bfs_by_level(graph: dict, start: str) -> list[list]:
"""
Returns a list of levels, where each level is a list of nodes
at that depth from the start node.
"""
visited = set([start])
queue = deque([start])
levels = []
while queue:
level_size = len(queue) # Snapshot: how many nodes are in this level
current_level = []
for _ in range(level_size): # Process exactly this many nodes
node = queue.popleft()
current_level.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
levels.append(current_level)
return levels
## Example usage with the same graph from before:
## Result: [['A'], ['B', 'C'], ['D', 'E', 'F']]
## Level 0: ['A']
## Level 1: ['B', 'C']
## Level 2: ['D', 'E', 'F']
Approach 2: Store Depth Alongside Each Node
Alternatively, store a (node, depth) tuple in the queue. This is often cleaner for problems that need to return a single minimum distance rather than the full level structure.
from collections import deque
def shortest_path_length(graph: dict, start: str, target: str) -> int:
"""
Returns the minimum number of edges to travel from start to target.
Returns -1 if no path exists.
"""
visited = set([start])
queue = deque([(start, 0)]) # Each entry is (node, depth)
while queue:
node, depth = queue.popleft()
if node == target:
return depth # First time we reach target = shortest path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, depth + 1)) # Increment depth
return -1 # Target unreachable
## Example: shortest path from 'A' to 'F'
## A β C β F = 2 steps
print(shortest_path_length(graph, 'A', 'F')) # 2
π‘ Pro Tip: For LeetCode problems involving grids (2D arrays), BFS level-tracking is the go-to strategy for "minimum steps" problems like Shortest Path in Binary Matrix (LC 1091) or 01 Matrix (LC 542). The grid cells become nodes, and adjacent cells (up, down, left, right) become edges. The level number at which you first reach the target is your answer.
Choosing Between BFS and DFS: A Decision Framework
Knowing how to implement BFS and DFS is necessary but not sufficient. The skill that separates good engineers from great ones is knowing which to reach for given a particular problem. Here is a practical decision framework:
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β GRAPH TRAVERSAL DECISION TREE β
β β
β Does the problem ask for SHORTEST PATH or MIN STEPS? β
β βββ Yes β BFS β
β
β βββ No β Continue... β
β β
β Does the problem explore ALL paths or require BACKTRACKING?β
β βββ Yes β DFS β
β
β βββ No β Continue... β
β β
β Does the problem ask for LEVEL-BY-LEVEL processing? β
β βββ Yes β BFS β
β
β βββ No β Continue... β
β β
β Is the solution likely CLOSE TO THE SOURCE (shallow tree)?β
β βββ Yes β BFS β
(finds it fast in early levels) β
β βββ No β DFS may use less memory β
β β
β Is the graph very WIDE (high branching factor)? β
β βββ Yes β DFS β
(BFS queue grows too large) β
β βββ No β Either works; prefer BFS for safety β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
| π Criterion | π― Choose BFS | π§ Choose DFS |
|---|---|---|
| π Goal | Shortest path / min steps | Any path / all paths |
| π§ Structure | Level-by-level processing | Deep exploration / backtracking |
| π§ Memory | High if graph is wide | High if graph is deep |
| π― Target location | Close to source (shallow) | Far from source (deep) |
| π Implementation | Queue (iterative) | Stack or recursion |
| π Cycle safety | Both need a visited set | Both need a visited set |
π‘ Real-World Example: Think about how a GPS navigation app works. Finding the fastest route from point A to point B resembles BFS (or Dijkstra's for weighted roads). But generating all possible routes for a hiking trail app might lean on DFS with backtracking, because you want to enumerate every possible path through the trail network, not just the shortest one.
π§ Mnemonic: BFS = Broad first (wide before deep). DFS = Deep first (down before wide). When you want Best distance, use BFS.
Putting It All Together: BFS in a Grid
Grid problems are among the most common BFS applications on LeetCode. The translation from "graph" to "grid" is straightforward: each cell (row, col) is a node, and its up/down/left/right neighbors are its edges. Here is a complete worked example finding the shortest path through a binary grid (0 = open, 1 = blocked):
from collections import deque
from typing import List
def shortest_path_binary_matrix(grid: List[List[int]]) -> int:
"""
LC 1091: Return the length of the shortest clear path from
top-left (0,0) to bottom-right (n-1, n-1) in a binary grid.
A clear path has only 0-valued cells. Return -1 if none exists.
"""
n = len(grid)
# Edge case: start or end is blocked
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
# 8-directional movement (including diagonals)
directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
# Queue stores (row, col, path_length)
queue = deque([(0, 0, 1)])
grid[0][0] = 1 # Mark visited by modifying in-place (common grid trick)
while queue:
row, col, length = queue.popleft()
if row == n - 1 and col == n - 1:
return length # Reached destination β BFS guarantees this is shortest
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# Check bounds and whether cell is open
if 0 <= new_row < n and 0 <= new_col < n and grid[new_row][new_col] == 0:
grid[new_row][new_col] = 1 # Mark visited before enqueuing β
queue.append((new_row, new_col, length + 1))
return -1 # No path found
## Test case:
## 0 0 0
## 1 1 0
## 1 1 0
grid = [[0,0,0],[1,1,0],[1,1,0]]
print(shortest_path_binary_matrix(grid)) # 4
Notice how the grid modification trick (grid[r][c] = 1) serves as our visited set directly β a common space-saving pattern when modifying the input is allowed. When it is not (be careful to read problem constraints!), use a separate visited = set() of (row, col) tuples.
β οΈ Common Mistake β Not Checking Bounds: In grid BFS, always validate 0 <= new_row < rows and 0 <= new_col < cols before accessing grid[new_row][new_col]. Accessing out-of-bounds indices raises an IndexError, and Python's negative indexing can cause subtle bugs where -1 wraps around to the last row or column rather than throwing an error.
BFS in Context: Representative LeetCode Problems
To make this concrete, here is a map of BFS problem archetypes you will encounter repeatedly:
π Quick Reference Card: BFS Problem Patterns
| π― Pattern | π Example Problem | π§ BFS Role |
|---|---|---|
| π Shortest path in grid | LC 1091, LC 542 | Min steps = level number |
| π§ Level-order traversal | LC 102 (Binary Tree) | Process nodes by depth |
| π Word transformation | LC 127 Word Ladder | Each word = node, 1 edit = edge |
| π§ Island / component size | LC 695 Max Area of Island | BFS expands each component |
| π― Multi-source BFS | LC 994 Rotting Oranges | Enqueue all sources at once |
| π Topological ordering | LC 207 Course Schedule | Kahn's algorithm = BFS variant |
The multi-source BFS pattern deserves special mention. In Rotting Oranges, every initially-rotten orange is a source. Instead of picking one start node, you enqueue all sources simultaneously at level 0. The BFS then propagates outward from all of them in parallel β exactly modeling the simultaneous spread of rot. This is a powerful generalization that turns what seems like a complex simulation into a clean, single-pass BFS.
π‘ Pro Tip: Whenever a problem says "all X spread simultaneously" or "minimum time for all cells to be affected," reach for multi-source BFS immediately. Initialize the queue with every source at once, set their distances to 0, and let BFS do the rest.
Summary: BFS at a Glance
BFS is not merely a traversal algorithm β it is a guarantee. It guarantees level-by-level exploration. It guarantees shortest paths in unweighted graphs. It guarantees that by the time you process any node, you have already considered every possible shorter route to it. These guarantees make BFS the right tool anytime the problem has a notion of "minimum" baked into it.
The implementation pillars are simple and repeatable:
π§ Use collections.deque for O(1) popleft.
π Mark nodes visited before enqueuing them, never after.
π§ Track levels with a size-snapshot loop when level identity matters.
π― Use tuple entries (node, depth) when you need depth alongside each node.
π Translate grid problems to graph problems: cell = node, adjacency = edge.
With DFS and BFS both in your toolkit β and a clear decision framework for choosing between them β you are equipped to tackle the broad majority of graph traversal problems on LeetCode. In the next section, we will consolidate that knowledge by examining the most common pitfalls developers encounter and how to defend against them systematically.
Common Pitfalls and Best Practices in Graph Traversal
Even developers who fully understand the theory of DFS and BFS can watch their solutions fail on LeetCode due to a handful of recurring, subtle mistakes. These aren't random errors β they cluster around a few predictable failure modes that appear again and again across graph problems. This section dissects each one with concrete before-and-after comparisons so you can recognize the pattern, fix it, and never fall into the same trap twice.
Think of this section as your graph traversal immune system. Once you've seen these bugs up close, your brain will flag them automatically before they ever reach your submitted code.
Pitfall 1: Forgetting to Mark Nodes as Visited Before Recursing
Visited marking is the mechanism that prevents your traversal from revisiting nodes it has already processed. In a graph with cycles, forgetting this step doesn't just cause redundant work β it causes infinite recursion or an infinite loop that will crash your program or trigger a time-limit exceeded (TLE) verdict.
The most common version of this mistake looks innocent: you mark a node as visited after you've done something with it, perhaps at the end of the DFS function. This feels logical β "I just finished processing this node, so now I'll mark it done." But in a cyclic graph, by the time you want to mark it, you've already recursed back into it.
Consider this graph with a cycle:
A β B β C
β |
βββββββββ
If you start DFS at A without marking A visited before recursing into B, then C will recurse back into A, which recurses into B again, which recurses into C again β forever.
β Wrong: Marking visited after the recursive call
def dfs_broken(node, graph, visited):
# Process the node first
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_broken(neighbor, graph, visited)
# β οΈ TOO LATE: marking visited after recursion
# On a cyclic graph, we've already re-entered this node
visited.add(node)
β Correct: Marking visited immediately upon entry
def dfs_correct(node, graph, visited):
# Mark visited the INSTANT we enter this node
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_correct(neighbor, graph, visited)
# No need to mark visited here β it's already done
π― Key Principle: Mark a node as visited the moment you decide to process it, not after. The visited set is a "we've claimed this node" flag, not a "we've finished this node" flag.
π§ Mnemonic: Think of visited marking like locking a door behind you when you enter a room. You lock it when you enter, not after you've explored everything inside.
Pitfall 2: Marking Visited When Dequeued Instead of When Enqueued (BFS)
This is arguably the most counterintuitive pitfall in graph traversal, and it's specific to BFS. The mistake: you check and mark a node as visited only when you pull it out of the queue (dequeue), rather than when you add it to the queue (enqueue).
Why does this matter? Because a node can sit in the queue multiple times before it's ever dequeued. If two neighbors both point to the same node and you haven't marked it yet, you'll add it to the queue twice. When you eventually process it, you'll process it twice β with all the cascading problems that entails.
Graph:
A
/ \
B C
\ /
D
Here, both B and C point to D. In BFS starting from A:
- You enqueue B and C (mark them visited)
- You dequeue B, and enqueue D
- You dequeue C, and enqueue D again (if you only mark visited on dequeue, D isn't marked yet!)
- Now D is in the queue twice
β Wrong: Mark visited on dequeue
from collections import deque
def bfs_broken(start, graph):
queue = deque([start])
visited = set() # NOT adding start here
while queue:
node = queue.popleft()
# β οΈ Marking visited here is too late
if node in visited:
continue # This band-aid check helps but is not the right pattern
visited.add(node)
print(node)
for neighbor in graph[node]:
queue.append(neighbor) # Duplicate entries can accumulate
β Correct: Mark visited on enqueue
from collections import deque
def bfs_correct(start, graph):
visited = {start} # Mark the start node immediately
queue = deque([start]) # Then enqueue it
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # Mark BEFORE enqueuing
queue.append(neighbor) # Then enqueue
β οΈ Common Mistake: Some developers add a continue check at the top of the while loop as a workaround ("if already visited, skip"). This prevents duplicate processing but doesn't prevent your queue from bloating to O(VΒ²) size on dense graphs β a performance disaster.
π‘ Pro Tip: The correct mental model is: enqueue = commit. The moment you decide a node belongs in BFS exploration, mark it. Don't wait for it to reach the front of the line.
Pitfall 3: Off-by-One Errors in Grid-Based Graph Traversal
Many LeetCode problems represent graphs implicitly as 2D grids β problems like Number of Islands, Rotting Oranges, or Word Search. In these problems, the graph has no explicit adjacency list; instead, neighbors are computed on the fly using directional offsets.
This is where off-by-one errors and incorrect boundary checks become your enemy. The two most common mistakes:
- Wrong boundary conditions β using
<= rowsinstead of< rows, or forgetting to check for negative indices - Incorrect direction arrays β accidentally including diagonal neighbors when only cardinal directions are needed, or vice versa
Grid (3x4):
[0][0] [0][1] [0][2] [0][3]
[1][0] [1][1] [1][2] [1][3]
[2][0] [2][1] [2][2] [2][3]
Valid indices: row β [0, 2], col β [0, 3]
β Wrong: Boundary check with off-by-one
def dfs_grid_broken(grid, row, col, visited):
rows, cols = len(grid), len(grid[0])
# β οΈ Off-by-one: should be < rows and < cols, not <=
if row < 0 or row <= rows or col < 0 or col <= cols:
return
if (row, col) in visited or grid[row][col] == 0:
return
visited.add((row, col))
# Neighbors β but wait, are these all four cardinal directions?
# β οΈ Missing the upward direction!
dfs_grid_broken(grid, row + 1, col, visited) # down
dfs_grid_broken(grid, row - 1, col, visited) # up
dfs_grid_broken(grid, row, col + 1, visited) # right
# dfs_grid_broken(grid, row, col - 1, visited) -- accidentally deleted!
β Correct: Clean grid DFS with explicit direction array
def dfs_grid_correct(grid, row, col, visited):
rows, cols = len(grid), len(grid[0])
# Boundary check: strict less-than for both dimensions
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if (row, col) in visited or grid[row][col] == 0:
return
visited.add((row, col))
# Explicit direction array: easy to audit and modify
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # right, left, down, up
for dr, dc in directions:
dfs_grid_correct(grid, row + dr, col + dc, visited)
π― Key Principle: Always define your direction offsets as an explicit array. This makes it trivial to audit ("do I have all 4 cardinal directions?"), easy to extend ("do I need 8 directions including diagonals?"), and impossible to accidentally omit one.
π‘ Mental Model: Think of a grid cell as a graph node, and its up/down/left/right neighbors as its adjacency list β one that you compute dynamically. All the same DFS/BFS rules apply; only the neighbor-generation step is different.
π€ Did you know? Many grid traversal solutions on LeetCode fail not because of the algorithm logic but purely because of a <= that should be <. A habit of always writing boundary checks as row < 0 or row >= rows (using strict >=) will save you countless debugging sessions.
Pitfall 4: Mutating Input Data as a Visited Marker
A common optimization in grid problems is to mutate the input grid itself to mark visited cells β for example, setting a cell to 0 or '#' after visiting it, instead of maintaining a separate visited set. This approach has real advantages but also serious risks that developers often underestimate.
Advantages of in-place mutation:
- π§ Saves O(V) memory β no separate visited structure needed
- π§ Often slightly faster in practice due to better cache behavior
- π§ Common in competitive programming and accepted in many LeetCode solutions
Risks of in-place mutation:
- β οΈ The original input is permanently destroyed β a problem if you need it later
- β οΈ Fails in multi-traversal problems where you need to reset state between runs
- β οΈ Creates subtle bugs in backtracking problems where you need to undo visited marking
- β οΈ Makes your code harder to test and debug
## β οΈ In-place mutation approach β fast but destructive
def dfs_mutating(grid, row, col):
rows, cols = len(grid), len(grid[0])
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] != '1': # Already visited or water
return
grid[row][col] = '#' # Mutate to mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs_mutating(grid, row + dr, col + dc)
# β οΈ Original grid is now permanently altered
## β
Separate visited set β clean and non-destructive
def dfs_clean(grid, row, col, visited):
rows, cols = len(grid), len(grid[0])
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if (row, col) in visited or grid[row][col] != '1':
return
visited.add((row, col)) # Non-destructive marking
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs_clean(grid, row + dr, col + dc, visited)
# grid remains unchanged
π Quick Reference Card: Mutation vs. Separate Visited Set
| π In-Place Mutation | β Separate Visited Set | |
|---|---|---|
| π¦ Memory | O(1) extra | O(V) extra |
| π§ Input preserved? | β No | β Yes |
| π― Good for backtracking? | β No | β Yes |
| β‘ Speed | Slightly faster | Minimal overhead |
| π Readability | Context-dependent | Generally clearer |
π‘ Pro Tip: In a LeetCode interview setting, start with a separate visited set. Mention the in-place mutation optimization explicitly as a trade-off you're aware of. This shows both correctness and algorithmic sophistication.
Pitfall 5: Failing to Handle Disconnected Graphs
This is perhaps the most conceptually important pitfall on this list, and it affects a surprising number of LeetCode solutions. A disconnected graph is a graph where not all nodes can be reached from a single starting point β there are isolated "islands" of nodes with no paths between them.
Disconnected Graph:
Component 1: Component 2: Component 3:
A --- B D F
| | |
C E G --- H
If you start DFS or BFS from node A, you'll perfectly traverse component 1 (A, B, C). But D, E, F, G, and H are completely unreachable. If your problem requires visiting every node β for example, detecting all connected components, finding all nodes that match some condition, or counting islands β a single traversal call will silently miss entire sections of the graph.
The fix is straightforward: wrap your traversal in an outer loop that iterates over all possible starting nodes, launching a new traversal from any node that hasn't been visited yet.
β Wrong: Single traversal call
def count_components_broken(n, edges):
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
# β οΈ Only starts from node 0 β misses disconnected components!
dfs(0)
return len(visited) # Wrong: may not include all nodes
β Correct: Outer loop over all nodes
def count_components_correct(n, edges):
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
component_count = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
# β
Outer loop ensures we visit every node,
# launching fresh DFS from any unvisited node
for node in range(n):
if node not in visited:
dfs(node) # Traverses one full component
component_count += 1 # Each fresh start = new component
return component_count
This outer loop pattern is the standard approach for:
- π§ Counting connected components
- π Finding all islands in a grid
- π§ Detecting isolated nodes
- π― Running any "global" graph analysis where all nodes matter
For grid problems, the same principle applies β instead of iterating over nodes by index, you iterate over every cell:
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
islands = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if (r, c) in visited or grid[r][c] == '0':
return
visited.add((r, c))
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r + dr, c + dc)
# β
Outer double loop covers every cell in the grid
for r in range(rows):
for c in range(cols):
if (r, c) not in visited and grid[r][c] == '1':
dfs(r, c) # Explore one full island
islands += 1 # Count it
return islands
π‘ Real-World Example: Consider a social network analysis tool that needs to find all "cliques" β groups of people who know each other but have no connections to other groups. A single BFS from one person would completely miss anyone outside their social bubble. The outer loop is what lets you enumerate every isolated community.
π― Key Principle: A traversal algorithm answers the question "what can I reach from here?" If your problem requires reasoning about the entire graph, you must ensure you've started from somewhere within every component.
Bringing It All Together: A Defensive Coding Checklist
Before you submit any graph traversal solution, run through this mental checklist:
β
GRAPH TRAVERSAL DEFENSIVE CHECKLIST
β‘ 1. VISITED MARKING (DFS)
β Am I marking visited at the START of the function, before recursing?
β‘ 2. VISITED MARKING (BFS)
β Am I marking visited when I ENQUEUE, not when I dequeue?
β Did I mark the START NODE before adding it to the queue?
β‘ 3. GRID BOUNDARIES
β Are my boundary checks using strict < (not <=)?
β Do I check row < 0, row >= rows, col < 0, col >= cols?
β Did I use an explicit directions array I can visually audit?
β‘ 4. INPUT MUTATION
β Does this problem require me to preserve the input?
β If I mutate in-place, does the algorithm need to undo mutations (backtracking)?
β‘ 5. DISCONNECTED GRAPHS
β Could the graph have multiple components?
β Does my solution need to visit ALL nodes or just reachable ones?
β If all nodes matter, do I have an outer loop?
π§ Mnemonic: Remember "VIGMD" β Visited early, Inqueue-mark, Grid bounds, Mutation trade-offs, Disconnected loops. Five letters, five pitfalls, zero surprises.
β οΈ Common Mistake: Developers often test their solutions on the sample inputs provided, which are usually small, connected, and acyclic graphs designed to be friendly. These samples almost never expose the pitfalls above. Always deliberately construct a test case with a cycle, a disconnected component, and edge grid cells to stress-test your solution before submitting.
Mastering these pitfalls isn't just about avoiding bugs β it's about building the kind of systematic, defensive thinking that lets you approach any graph problem with confidence. The algorithms themselves (DFS and BFS) are simple. What separates clean, correct solutions from buggy ones is almost always one of the five failure modes covered in this section.
Key Takeaways and Your Graph Traversal Cheat Sheet
You came into this lesson knowing that graphs exist. You leave it knowing how to think in graphs β how to look at a problem and immediately identify its nodes, edges, and search goal before writing a single line of code. That shift in perspective is the real achievement here. Graph traversal is not one algorithm; it is a mental operating system for a whole category of problems, and you now have that OS installed.
This final section ties everything together into frameworks you can carry into every graph problem you encounter on LeetCode. Bookmark it, print it, or paste it into your notes β this is the reference sheet you will return to again and again.
The Three Questions to Ask Before Writing Code
Before you touch the keyboard on any graph problem, stop and answer three questions explicitly. Writing them down in a comment at the top of your solution file takes thirty seconds and saves you from five minutes of confused backtracking.
π― Key Principle: Every graph problem is secretly a fill-in-the-blank for these three questions:
1. What are the NODES? (What are the individual units I'm visiting?)
2. What are the EDGES? (What counts as a connection between two nodes?)
3. What am I SEARCHING FOR? (Am I finding a path? Counting components? Checking reachability?)
Let's make this concrete with the three canonical LeetCode problems this lesson maps to:
| Problem | Nodes | Edges | Searching For |
|---|---|---|---|
| Number of Islands | Each (row, col) cell in the grid |
Adjacent '1' cells (up/down/left/right) |
Count of connected components |
| Clone Graph | Each Node object |
The .neighbors list on each node |
A complete deep copy of the structure |
| Course Schedule | Each course number 0..n-1 |
A prerequisite relationship [a, b] means bβa |
Whether a cycle exists |
Notice something powerful: once you fill in that table, the implementation almost writes itself. Number of Islands wants a component count β run DFS/BFS on each unvisited land cell, increment a counter each time you start a new traversal. Clone Graph wants a structural copy β DFS with a visited dictionary that maps original nodes to their clones. Course Schedule wants cycle detection β DFS with a three-color state (unvisited, in-progress, done).
π‘ Pro Tip: If you can't answer question 1 or 2, you don't understand the problem yet. Re-read the problem statement before coding, not after.
DFS vs. BFS: The Side-by-Side Comparison
The single most common confusion in graph problems is choosing the wrong traversal. Here is a complete, direct comparison you can use as a decision guide.
π Quick Reference Card: DFS vs. BFS
| Property | π΅ DFS | π BFS |
|---|---|---|
| βοΈ Mechanism | Go as deep as possible, backtrack | Explore all neighbors at current depth first |
| ποΈ Data Structure | Stack (call stack or explicit) | Queue (collections.deque) |
| β±οΈ Time Complexity | O(V + E) | O(V + E) |
| π§ Space Complexity | O(V) worst case (deep recursion / tall stack) | O(V) worst case (wide frontier queue) |
| π Shortest Path Guarantee | β No | β Yes (unweighted graphs) |
| π Finds Any Path | β Yes | β Yes |
| π― Best For | Cycle detection, topological sort, connected components, backtracking, DFS tree | Shortest path (unweighted), level-order traversal, "minimum steps" problems |
| β οΈ Watch Out For | Stack overflow on very deep graphs (use iterative DFS) | Memory usage on very wide graphs |
π§ Mnemonic: DFS goes Deep. BFS goes Broad. When the problem says "shortest" or "minimum steps," think Broad first.
π€ Did you know? Both DFS and BFS have identical worst-case time and space complexity of O(V + E). The choice between them is almost never about raw performance β it is about which one naturally gives you the answer structure you need.
The Universal Graph Traversal Template
Every graph problem you solve on LeetCode can be traced back to one of two templates below. These are not toy examples β they are production-grade patterns used directly in interview solutions. Study them until you can reproduce them from memory.
Template 1: DFS (Recursive)
def solve(graph, start):
"""
Universal DFS template.
- graph: adjacency list {node: [neighbors]}
- start: the node to begin traversal from
"""
visited = set() # Tracks nodes we've already processed
def dfs(node):
# Base case: skip if already visited
if node in visited:
return
# Mark BEFORE recursing to prevent infinite loops
visited.add(node)
# βοΈ DO YOUR WORK HERE (collect result, check condition, etc.)
print(f"Visiting: {node}")
# Recurse into all unvisited neighbors
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
dfs(start)
return visited # Or whatever you're accumulating
## ββ Adaptation for grid problems (e.g., Number of Islands) ββ
def dfs_grid(grid, row, col, visited):
rows, cols = len(grid), len(grid[0])
# Bounds check + wall check + visited check (one combined guard)
if (row < 0 or row >= rows or
col < 0 or col >= cols or
grid[row][col] == '0' or
(row, col) in visited):
return
visited.add((row, col))
# Explore all 4 directions
directions = [(0,1),(0,-1),(1,0),(-1,0)]
for dr, dc in directions:
dfs_grid(grid, row + dr, col + dc, visited)
This template handles the two most common graph shapes: adjacency-list graphs (like Clone Graph or Course Schedule) and implicit grid graphs (like Number of Islands or Surrounded Regions). The structural logic is identical β only the neighbor-generation step changes.
Template 2: BFS (Iterative with deque)
from collections import deque
def solve_bfs(graph, start):
"""
Universal BFS template.
- graph: adjacency list {node: [neighbors]}
- start: the source node
Returns: shortest distances from start to all reachable nodes
"""
visited = set([start]) # Mark start as visited IMMEDIATELY on enqueue
queue = deque([start]) # Initialize queue with starting node
distance = {start: 0} # Optional: track level/distance
while queue:
node = queue.popleft() # Always popleft for FIFO order
# βοΈ DO YOUR WORK HERE
print(f"Visiting: {node}, distance: {distance[node]}")
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor) # Mark on ENQUEUE, not dequeue
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
## ββ Multi-source BFS (useful for problems like "01 Matrix") ββ
def multi_source_bfs(graph, sources):
"""
Start BFS from multiple nodes simultaneously.
Useful when you have multiple "origin" points.
"""
visited = set(sources)
queue = deque(sources) # Seed queue with ALL starting nodes at once
distance = {s: 0 for s in sources}
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
β οΈ Critical Point to Remember: Mark nodes as visited when you enqueue them, not when you dequeue them. This single rule prevents the same node from being added to the queue multiple times and is the most common source of TLE (Time Limit Exceeded) on BFS problems.
π‘ Mental Model: Think of BFS like ripples in a pond. You drop a stone (your source node), and ripples spread outward one ring at a time. Every node in ring 1 is at distance 1, ring 2 at distance 2, and so on. Multi-source BFS is like dropping several stones simultaneously.
How the Lesson Maps to the Three Canonical Problems
Let's close the loop explicitly. Here is how every concept from this lesson directly applies to three problems you will almost certainly encounter.
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β CONCEPT β PROBLEM MAPPING β
β βββββββββββββββ¦ββββββββββββββββββββ¦βββββββββββββββββββββββββββββββ£
β Concept β Problem β How It Applies β
β βββββββββββββββ¬ββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ£
β Grid as graph β Number of Islands β (r,c) cells are nodes; β
β β β 4-directional adjacency β
β β β defines edges β
β βββββββββββββββ¬ββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ£
β visited dict β Clone Graph β Maps originalβclone; β
β as memo β β prevents re-cloning cycles β
β βββββββββββββββ¬ββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ£
β Cycle detectionβ Course Schedule β 3-color DFS state tracks β
β via DFS state β β in-progress nodes β
β βββββββββββββββ¬ββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ£
β Component β Number of Islands β Each DFS/BFS from an β
β counting β β unvisited '1' = one island β
β βββββββββββββββ¬ββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ£
β Adjacency listβ Clone Graph β .neighbors IS the adj list; β
β traversal β β traverse and rebuild it β
ββββββββββββββββ©ββββββββββββββββββββ©βββββββββββββββββββββββββββββββ
Number of Islands (LeetCode 200) is the ideal first problem to solve after this lesson. It forces you to work with an implicit graph (a grid), practice the boundary-check guard clause, and use component counting β all in a single clean problem. The DFS template above adapts to it with fewer than ten lines of modification.
Clone Graph (LeetCode 133) tests whether you understand the visited dictionary's dual role: it prevents revisiting nodes and serves as a lookup table for already-created clones. This is a nuance that separates understanding traversal from mastering it.
Course Schedule (LeetCode 207) is where cycle detection lives. The key insight is that you need three states β 0 (unvisited), 1 (currently in DFS stack), 2 (fully processed) β not just a boolean visited set. If you reach a node in state 1 during DFS, you've found a back edge, which means a cycle, which means the schedule is impossible.
π‘ Real-World Example: Course Schedule is literally how build systems (like make or gradle) detect circular dependencies. If library A requires library B which requires library A, the build fails. The algorithm checking this is exactly the DFS cycle detection you just learned.
Your Recommended Practice Strategy
Knowing what to practice matters as much as knowing how to practice. Here is the sequenced approach that builds mastery efficiently:
π§ Phase 1 β Traversal Isolation (Week 1) Solve problems where the only skill required is traversal. Your goal is to make the template feel automatic.
- π Number of Islands (LeetCode 200) β DFS on a grid
- π Flood Fill (LeetCode 733) β BFS or DFS on a grid
- π Find if Path Exists in Graph (LeetCode 1971) β basic DFS/BFS on adjacency list
- π Keys and Rooms (LeetCode 841) β DFS with a visited set
π§ Phase 2 β Single-Concept Extensions (Week 2) Add one new concept on top of traversal per problem.
- π― Clone Graph (LeetCode 133) β traversal + hash map memo
- π― Max Area of Island (LeetCode 695) β traversal + accumulator
- π― 01 Matrix (LeetCode 542) β multi-source BFS
- π― Rotting Oranges (LeetCode 994) β multi-source BFS with a counter
π§ Phase 3 β Compound Graph Problems (Week 3+) Now tackle problems that require traversal plus another algorithmic idea.
- π§ Course Schedule (LeetCode 207) β DFS + cycle detection
- π§ Course Schedule II (LeetCode 210) β DFS + topological sort
- π§ Pacific Atlantic Water Flow (LeetCode 417) β reverse multi-source BFS
- π§ Word Ladder (LeetCode 127) β BFS on an implicit graph
π‘ Pro Tip: When you solve a problem, always ask yourself: "Could I have solved this with the other traversal?" Answering that question for every problem builds intuition faster than solving twice as many problems.
β οΈ Common Mistake: Jumping straight to compound problems before traversal feels automatic. If you're still thinking about how to implement DFS while also thinking about what the cycle-detection logic should be, you will confuse yourself. Isolate the pattern first.
The Complete One-Page Cheat Sheet
Here is everything distilled into a single reference you can scan in sixty seconds before starting a graph problem.
π Quick Reference Card: Graph Traversal Master Summary
π΅ Step 1 β Ask the Three Questions
β Nodes: What am I visiting?
β Edges: What counts as "connected"?
β Goal: What am I looking for?
π΅ Step 2 β Choose Your Traversal
Need SHORTEST PATH or MINIMUM STEPS? β BFS
Need CYCLE DETECTION or TOPO SORT? β DFS
Need COMPONENT COUNT? β Either (DFS simpler)
Need LEVEL-BY-LEVEL processing? β BFS
Anything else? β DFS (simpler code)
π΅ Step 3 β Apply the Template
DFS: visited set + recursive dfs(node) function
BFS: visited set + deque + while queue loop
Grid: replace neighbor list with 4-directional bounds-checked expansion
π΅ Step 4 β Remember the Rules
β
Mark visited BEFORE recursing (DFS) or ON ENQUEUE (BFS)
β
Check visited BEFORE adding to queue or recursing
β
Use a set for O(1) visited lookups
β
Use deque, not list, for O(1) queue popleft
β οΈ Very deep graphs β switch to iterative DFS to avoid stack overflow
β οΈ Cycle detection β use 3-color state, not boolean visited
What You Now Understand
Let's be explicit about the cognitive shift this lesson produced. Before this lesson, a problem like "Given a 2D grid, count the number of islands" might have felt like a unique, specialized puzzle. After this lesson, you see it for what it is: a connected component count problem on an implicit grid graph, solvable in fifteen lines using the DFS template you now have memorized.
That generalization is the whole point. Here is what you have genuinely internalized:
- π§ Graph vocabulary β you can read any graph problem and immediately classify its structure (directed/undirected, weighted/unweighted, cyclic/acyclic, explicit/implicit)
- π§ Two implementation patterns β DFS (recursive and iterative) and BFS (queue-based), with working templates ready to deploy
- π― A decision framework β three questions and a decision tree that tell you which traversal to reach for
- π Pitfall awareness β you know about infinite loops, premature visited-marking, wrong data structures, and off-by-one boundary checks before you make those mistakes
- π Problem-to-pattern mapping β Number of Islands β component counting, Clone Graph β traversal with memoization, Course Schedule β cycle detection
π€ Did you know? Many of the most impressive technical systems in the world β Google's PageRank, GPS navigation, social network friend suggestions, dependency resolution in package managers β are fundamentally graph traversal algorithms operating at enormous scale. Every time you master a graph traversal pattern on LeetCode, you are learning the same conceptual machinery those systems are built on.
Next Steps
With graph traversal as your foundation, three natural directions open up:
Weighted graphs and shortest paths β Once BFS handles unweighted shortest paths, Dijkstra's algorithm extends the idea to weighted graphs. The mental model is the same; the data structure upgrades from a queue to a min-heap.
Topological sort β Course Schedule II asks you to produce the actual ordering, not just detect if one exists. This takes DFS cycle detection one step further into one of the most practically useful graph algorithms in software engineering.
Union-Find (Disjoint Set Union) β An alternative approach to connected-component problems that offers near-constant time operations for merging and querying components. Understanding when to choose Union-Find over DFS/BFS is the next level of graph problem pattern recognition.
β οΈ Final Critical Point: The templates in this lesson are starting points, not straitjackets. Every real graph problem will require some adaptation β a different visited structure, an additional piece of state tracked alongside the traversal, or a modified termination condition. The skill is recognizing which template you are adapting and why you are making each change. That metacognitive habit β knowing what you're doing and why β is what separates developers who can solve graph problems from developers who understand them.
You now belong in the second group. Go build something.