Python BFS Template
Breadth-first search visits nodes in order of distance from the start, which makes it the right tool for shortest-path-by-edge-count, level-order traversal, and 'fewest steps' search problems. Python's `collections.deque` gives you O(1) `popleft`, which is the difference between BFS and an O(n^2) accident. This entry covers the standard template, distance tracking, and a level-by-level variant.
343 views
8
from collections import deque, defaultdict
def bfs(graph, start):
"""Return nodes in BFS visit order from `start`."""
visited = {start}
order = []
queue = deque([start])
while queue:
node = queue.popleft()
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
# Build a small graph for the demo.
graph = defaultdict(list)
for u, v in [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6)]:
graph[u].append(v)
graph[v].append(u)
print(bfs(graph, 1)) # e.g. [1, 2, 3, 4, 5, 6]
print(bfs(graph, 6)) # e.g. [6, 5, 4, 2, 3, 1]
# Single-node graph and disconnected start.
lonely = defaultdict(list)
lonely[42] = []
print(bfs(lonely, 42)) # [42]BFS uses a FIFO queue: the first node enqueued is the first one dequeued. The crucial detail is marking a node visited when you enqueue it, not when you pop it; otherwise the same node can be enqueued many times by different neighbors. collections.deque gives O(1) popleft; using a plain list with pop(0) accidentally turns the algorithm into O(n^2) and is a top interview gotcha. The same loop body works for any iterable graph: dictionaries, adjacency matrices, or even on-the-fly neighbor functions.
from collections import deque, defaultdict
def shortest_distances(graph, source):
"""Distance in edges from `source` to every reachable node. Unreachable -> not in dict."""
dist = {source: 0}
queue = deque([source])
while queue:
node = queue.popleft()
for nbr in graph[node]:
if nbr not in dist:
dist[nbr] = dist[node] + 1
queue.append(nbr)
return dist
graph = defaultdict(list)
for u, v in [(1, 2), (1, 3), (2, 4), (3, 5), (4, 6), (5, 6)]:
graph[u].append(v)
graph[v].append(u)
graph[99] = [] # disconnected node
dist = shortest_distances(graph, 1)
print(sorted(dist.items()))
# [(1, 0), (2, 1), (3, 1), (4, 2), (5, 2), (6, 3)]
print(99 in dist) # False (unreachable)
print(dist.get(99, 'no path')) # 'no path'
# Single-node distance.
print(shortest_distances(graph, 99)) # {99: 0}Distances fall out of BFS for free: the first time you see a node it must be at the smallest possible edge count (BFS visits in order of distance), so set dist[nbr] = dist[node] + 1 at the moment you enqueue it. Nodes that never appear in the dict are unreachable from the source. This is the right algorithm for any 'fewest moves' question on an unweighted graph: chess knight tours, word ladders, smallest number of bus transfers. For weighted graphs you need Dijkstra instead.
from collections import deque, defaultdict
def bfs_by_level(graph, start):
"""Yield each BFS level as a list of nodes."""
visited = {start}
level = [start]
while level:
yield level
next_level = []
for node in level:
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
next_level.append(nbr)
level = next_level
graph = defaultdict(list)
for u, v in [(1, 2), (1, 3), (2, 4), (3, 5), (4, 6), (5, 6), (6, 7)]:
graph[u].append(v)
graph[v].append(u)
for i, lvl in enumerate(bfs_by_level(graph, 1)):
print(f'level {i}: {sorted(lvl)}')
# level 0: [1]
# level 1: [2, 3]
# level 2: [4, 5]
# level 3: [6]
# level 4: [7]
# Empty start handling: degenerate graph with one node.
solo = defaultdict(list)
solo[42] = []
print(list(bfs_by_level(solo, 42))) # [[42]]When the algorithm cares about levels (binary tree level order, 'snapshot of frontier per round'), keep a list of the current level instead of a single queue. After processing every node in level, build next_level from their unvisited neighbors and yield the snapshot. This avoids the bookkeeping of attaching a (node, depth) tuple to every queue entry and naturally separates rounds. Use it for animated traversals, k-th-level queries, and any 'closest things first, ties broken arbitrarily' problem.