Graph Traversal: BFS & DFS
Model relationships as nodes and edges, then traverse them. See breadth-first and depth-first exploration diverge.
A graph is just nodes connected by edges — the most flexible data structure there is. Social networks, road maps, package dependencies, the web, and the state space of a puzzle are all graphs. Master the two fundamental traversals and a huge swath of problems becomes approachable.
The two traversals answer “how do I visit every node reachable from a starting point?” — but they explore in very different orders. Toggle between them below and watch the difference.
Breadth-first search (BFS)
BFS explores in rings: all nodes one step away, then all nodes two steps away, and so on. It uses a queue (first-in, first-out). Because it reaches nodes in order of distance, BFS finds the shortest path in an unweighted graph — a property you’ll use constantly.
from collections import deque
def bfs(graph, start):
seen = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for nb in graph[node]:
if nb not in seen:
seen.add(nb)
queue.append(nb)
return seenDepth-first search (DFS)
DFS plunges down one path as far as it can, then backtracks and tries the next. It uses a stack — often the call stack via recursion. DFS is the natural choice for problems about connectivity, cycle detection, topological ordering, and exploring all configurations.
def dfs(graph, node, seen=None):
if seen is None:
seen = set()
seen.add(node)
for nb in graph[node]:
if nb not in seen:
dfs(graph, nb, seen)
return seenThe one rule that keeps traversals correct
Both traversals share a single non-negotiable: mark a node as seen before you explore it, and never enqueue/recurse into a seen node. Forget this and a graph with cycles will loop forever, or you’ll process the same node many times. In the animation, that’s the “already seen” check that keeps the frontier moving outward.
Choosing between them
| Use BFS when… | Use DFS when… |
|---|---|
| You need the shortest path (unweighted) | You need to explore/enumerate all paths |
| The answer is “close” to the start | You’re detecting cycles or ordering deps |
| The graph is wide but shallow | The graph is deep, or recursion is natural |
Where to go next
Weighted shortest paths swap BFS’s queue for a priority queue — that’s Dijkstra’s algorithm. Add a heuristic and you get A*. Both are BFS with a smarter notion of “closest,” so the mental model you just built carries directly forward.
Interview tip: the moment a problem involves reachability, connectivity, “levels,” or a grid you can move around, model it as a graph and ask “BFS or DFS?” before writing anything.
Pattern recognition
Variations
Worked problems
Each problem is the same traversal loop with a different definition of “neighbor” and a different reason for marking nodes as seen.
Number of Islands
Given a grid of water and land cells, count how many separate islands exist. Land connects horizontally or vertically, not diagonally.
Approach. Treat each land cell as a graph node. When you find unvisited land, you found a new island; DFS from it and mark the entire component so it is not counted again.
Show solution
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def dfs(r, c):
if r < 0 or r == rows or c < 0 or c == cols or grid[r][c] != "1":
return
grid[r][c] = "0"
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
islands += 1
dfs(r, c)
return islandsComplexity. O(rows · cols) time and O(rows · cols) worst-case recursion space. Each cell is visited at most once.
Clone Graph
Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. Each node has a value and a list of neighbors.
Approach. DFS the original graph and keep a map from original node to cloned node. The map prevents infinite recursion on cycles and ensures shared neighbors remain shared in the clone.
Show solution
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def clone_graph(node):
if node is None:
return None
clones = {}
def clone(cur):
if cur in clones:
return clones[cur]
copy = Node(cur.val)
clones[cur] = copy
for nb in cur.neighbors:
copy.neighbors.append(clone(nb))
return copy
return clone(node)Complexity. O(V + E) time and O(V) space. Every node is cloned once, and every adjacency-list entry is traversed once.
Rotting Oranges
Given a grid with empty cells, fresh oranges, and rotten oranges, each rotten orange turns adjacent fresh oranges rotten once per minute. Return the minutes needed to rot all fresh oranges, or -1 if some fresh orange can never be reached.
Approach. This is BFS by time layer. Seed the queue with all initially rotten oranges, because they spread simultaneously. Count fresh oranges; each time BFS rots one, decrement the count. The last processed minute is the answer if no fresh oranges remain.
Show solution
from collections import deque
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
q = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
q.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q:
r, c, minutes = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc, minutes + 1))
return minutes if fresh == 0 else -1Complexity. O(rows · cols) time and O(rows · cols) space. Every cell enters the queue at most once.