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 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]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