BFS: Shortest Path and Level Traversal
Use BFS to find the shortest path in an unweighted graph, solve word-ladder level by level, and clone a graph using a hash map.
BFS: Shortest Path and Level Traversal is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
BFS and Shortest Path in Unweighted Graphs
BFS finds the shortest path (fewest edges) in an unweighted graph because it explores nodes in order of increasing distance from the source. The first time a node is reached during BFS, it is via the shortest possible path. This property does not hold for DFS. For weighted graphs with non-negative weights, use Dijkstra's algorithm instead — BFS implicitly treats all edges as having weight 1.
from collections import deque, defaultdict
def shortest_path(graph, start, end):
if start == end:
return 0
visited = {start}
queue = deque([(start, 0)]) # (node, distance)
while queue:
node, dist = queue.popleft()
for neighbour in graph[node]:
if neighbour == end:
return dist + 1
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, dist + 1))
return -1 # no path found
graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,3),(1,4)]:
graph[u].append(v); graph[v].append(u)
print(shortest_path(graph, 0, 3)) # 1 (direct edge)
print(shortest_path(graph, 0, 4)) # 2 (0->1->4)Tracking the Actual Shortest Path
To reconstruct the actual path (not just its length), maintain a parent dictionary that records how each node was reached. When you reach the destination, trace back through the parent map from end to start and reverse the result. This adds O(V) space for the parent map but provides the full path in O(path_length) time after BFS completes.
from collections import deque, defaultdict
def shortest_path_with_route(graph, start, end):
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == end:
break
for nb in graph[node]:
if nb not in parent:
parent[nb] = node
queue.append(nb)
if end not in parent:
return [] # no path
# Reconstruct path by tracing back
path = []
node = end
while node is not None:
path.append(node)
node = parent[node]
return path[::-1] # reverse
graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,4),(4,3)]:
graph[u].append(v); graph[v].append(u)
print(shortest_path_with_route(graph, 0, 3)) # [0, 4, 3] or [0, 1, 2, 3]Word Ladder: BFS on Implicit Graph
Word Ladder (LeetCode #127) asks for the minimum number of single-character changes to transform a start word into an end word, where every intermediate word must be in a dictionary. This is a BFS on an implicit graph where nodes are words and edges connect words that differ by one letter. Generate all one-letter mutations and check if they are in the word set. BFS guarantees the minimum transformation sequence.
from collections import deque
def word_ladder(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
visited = {begin_word}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == end_word:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(word_ladder('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5Level Traversal: Tracking Distance
Level traversal groups nodes by their distance from the source, which is directly useful for problems that need per-level processing. Track distance either by storing it in the queue element as a tuple (node, dist), or by using the queue-size technique (record the queue size before each level, process exactly that many nodes, then increment a level counter). Both approaches give identical results.
from collections import deque, defaultdict
def bfs_levels(graph, start):
levels = {}
visited = {start}
queue = deque([start])
dist = 0
while queue:
# Process all nodes at current distance
for _ in range(len(queue)):
node = queue.popleft()
levels[node] = dist
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
dist += 1
return levels
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
graph[u].append(v); graph[v].append(u)
print(bfs_levels(graph, 0)) # {0:0, 1:1, 2:1, 3:2, 4:3}Clone Graph
Clone Graph (LeetCode #133) creates a deep copy of a connected undirected graph. Use BFS and a hash map mapping original nodes to their clones. When you first visit a node, create its clone and add it to the map. When processing neighbours, look up or create their clones and wire the edges. The hash map serves dual purpose: tracking visited nodes and mapping originals to copies.
from collections import deque
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 not node:
return None
old_to_new = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for nb in curr.neighbors:
if nb not in old_to_new:
old_to_new[nb] = Node(nb.val)
queue.append(nb)
old_to_new[curr].neighbors.append(old_to_new[nb])
return old_to_new[node]
# Build a simple graph: 1 -- 2 -- 3 -- 4 -- 1
n1 = Node(1); n2 = Node(2); n3 = Node(3); n4 = Node(4)
n1.neighbors = [n2, n4]; n2.neighbors = [n1, n3]
n3.neighbors = [n2, n4]; n4.neighbors = [n3, n1]
cloned = clone_graph(n1)
print(cloned.val, [n.val for n in cloned.neighbors]) # 1 [2, 4]Bidirectional BFS
Bidirectional BFS starts BFS from both the source and the destination simultaneously, expanding one level at a time from each end. When the two frontiers meet, you have found the shortest path. For large graphs, this reduces the search space from O(b^d) to O(2 * b^(d/2)) where b is the branching factor and d is the path length — a dramatic improvement for deeply connected graphs like word ladder with large dictionaries.
from collections import defaultdict
def word_ladder_bidir(begin, end, word_list):
word_set = set(word_list)
if end not in word_set:
return 0
front, back = {begin}, {end}
visited = {begin, end}
steps = 1
while front and back:
# Always expand the smaller frontier
if len(front) > len(back):
front, back = back, front
next_front = set()
for word in front:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nw = word[:i] + c + word[i+1:]
if nw in back: # frontiers met!
return steps + 1
if nw in word_set and nw not in visited:
visited.add(nw)
next_front.add(nw)
front = next_front
steps += 1
return 0
print(word_ladder_bidir('hit','cog',['hot','dot','dog','lot','log','cog'])) # 50-1 BFS for Weighted Graphs
0-1 BFS handles graphs where edge weights are only 0 or 1. Instead of a regular queue, use a deque: append to the back for edges with weight 1 (next level) and to the front for edges with weight 0 (same level). This gives O(V + E) shortest-path computation — faster than Dijkstra's O((V+E) log V) when weights are binary. Common in grid problems where some moves are free and others cost 1.
from collections import deque
def zero_one_bfs(graph, start, n):
# graph: list of (neighbour, weight) where weight is 0 or 1
dist = [float('inf')] * n
dist[start] = 0
dq = deque([start])
while dq:
node = dq.popleft()
for nb, w in graph[node]:
if dist[node] + w < dist[nb]:
dist[nb] = dist[node] + w
if w == 0:
dq.appendleft(nb) # same level
else:
dq.append(nb) # next level
return dist
# Simple test:
graph = [[(1, 0), (2, 1)], # node 0: free to 1, cost 1 to 2
[(3, 1)], # node 1: cost 1 to 3
[(3, 0)], # node 2: free to 3
[]]
print(zero_one_bfs(graph, 0, 4)) # [0, 0, 1, 1]Walls and Gates (Multi-Source BFS)
Walls and Gates fills each empty room with the distance to its nearest gate. Use multi-source BFS: initialise the queue with all gates (value 0) simultaneously and expand outward. Each cell's value is set to the level at which it is first reached. This O(mn) solution is more efficient than running BFS from each empty room separately, which would be O(m²n²).
from collections import deque
def walls_and_gates(rooms):
if not rooms:
return
rows, cols = len(rooms), len(rooms[0])
INF = float('inf')
queue = deque()
# Multi-source: all gates at distance 0
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0: # gate
queue.append((r, c))
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and rooms[nr][nc]==INF:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
rooms = [[float('inf'),-1,0,float('inf')],
[float('inf'),float('inf'),float('inf'),-1],
[float('inf'),-1,float('inf'),-1],
[0,-1,float('inf'),float('inf')]]
walls_and_gates(rooms)
print(rooms[0][0], rooms[1][1]) # 3, 2Snakes and Ladders BFS
Snakes and Ladders (LeetCode #909) is a BFS shortest-path problem on a number grid. Model the board as an unweighted graph where you can roll 1-6 from any square and may land on a snake or ladder that teleports you. BFS finds the minimum number of dice rolls. The key challenge is converting between 1D position and 2D board coordinates, accounting for the boustrophedon (alternating row direction) layout.
from collections import deque
def snakes_and_ladders(board):
n = len(board)
def get_board(pos):
r, c = divmod(pos - 1, n)
if r % 2 == 1: c = n - 1 - c # alternating direction
return board[n - 1 - r][c]
visited = {1}
queue = deque([(1, 0)])
while queue:
pos, moves = queue.popleft()
for dice in range(1, 7):
next_pos = pos + dice
if next_pos > n * n:
break
val = get_board(next_pos)
if val != -1:
next_pos = val # snake or ladder
if next_pos == n * n:
return moves + 1
if next_pos not in visited:
visited.add(next_pos)
queue.append((next_pos, moves + 1))
return -1
print('BFS models game as an unweighted shortest-path problem')BFS Complexity and Optimisations
BFS time complexity is O(V + E) because each vertex is enqueued once and each edge is examined a constant number of times. Space complexity is O(V) for the visited set and queue. For grid graphs, V = m*n and E = 4*m*n (each cell has 4 neighbours), so BFS on a grid is O(mn). Key optimisation: use a set for visited (O(1) lookup) not a list (O(n) lookup). Mark visited on enqueue, not on dequeue.
# BFS on a graph with V vertices and E edges:
# Time: O(V + E) -- each vertex and edge visited once
# Space: O(V) -- visited set + queue
# BFS on an m x n grid:
# V = m*n cells
# E <= 4*m*n edges (4 directions, max)
# Time: O(m*n)
# Space: O(m*n)
# Common pitfalls:
# 1. Marking visited on dequeue (not enqueue) -> same node queued multiple times
# 2. Using a list for visited -> O(n) membership check -> O(V*E) total
# 3. Not handling disconnected graph -> BFS from single source misses components
print('O(V+E) time, O(V) space -- mark visited on enqueue')Nearest 0 in Binary Matrix
01 Matrix (LeetCode #542) finds the distance from each cell to the nearest 0. Multi-source BFS from all 0s simultaneously gives the optimal O(mn) solution. Initialise the queue with all 0-cells at distance 0 and all 1-cells with distance infinity. BFS propagates distances outward from the 0s, setting each 1-cell's distance the first time it is reached (guaranteed to be the shortest).
from collections import deque
def update_matrix(mat):
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols:
if dist[r][c] + 1 < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
mat = [[0,0,0],[0,1,0],[1,1,1]]
result = update_matrix(mat)
for row in result: print(row) # [[0,0,0],[0,1,0],[1,2,1]]Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: BFS for shortest-path in unweighted graphs with parent tracking for route reconstruction, word ladder as a canonical BFS on an implicit graph, bidirectional BFS for large graphs, and multi-source BFS for problems with multiple starting points. Next up we apply DFS to connected components and flood fill.
Frequently asked questions
Is the “BFS: Shortest Path and Level Traversal” lesson free?
Yes — the full text of “BFS: Shortest Path and Level Traversal” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “BFS: Shortest Path and Level Traversal”?
Use BFS to find the shortest path in an unweighted graph, solve word-ladder level by level, and clone a graph using a hash map. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “BFS: Shortest Path and Level Traversal” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Graph Representations and Traversal Setup
- BFS: Shortest Path and Level Traversal
- DFS: Connected Components and Flood Fill
- Cycle Detection in Directed and Undirected Graphs