BFS：最短路径与层序遍历
使用 BFS 查找无权图中的最短路径，逐层解决单词接龙，并使用哈希映射克隆图。
BFS：最短路径与层序遍历 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
BFS 与无权图中的最短路径
BFS 能在无权图中找到最短路径（边数最少），因为它按照与源节点距离递增的顺序探索节点。在 BFS 中，节点第一次被到达时，所经过的路径一定是可能的最短路径。DFS 不具备这一性质。对于边权为非负数的加权图，请改用迪杰斯特拉算法——BFS 默认所有边的权重都为 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)跟踪实际的最短路径
若要还原实际路径（而不仅仅是路径长度），请维护一个父节点字典，记录每个节点是如何被到达的。当到达目标节点后，从终点沿着父节点映射回溯到起点，再将结果反转。这样会为父节点映射增加 O(V) 的空间，但 BFS 完成后可以在 O(路径长度) 的时间内得到完整路径。
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]单词接龙：隐式图上的 BFS
单词接龙（LeetCode #127）要求求出将起始单词转换为结束单词所需的最少单字母变更次数，并且每个中间单词都必须存在于字典中。这是在隐式图上执行的 BFS：节点是单词，边连接只相差一个字母的单词。请生成所有单字母变换，并检查它们是否位于单词集合中。BFS 可以保证得到最短的转换序列。
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'])) # 5逐层遍历：跟踪距离
逐层遍历按照节点与源节点之间的距离对节点分组，这对于需要按层处理的问题非常有用。您可以将距离作为元组 (node, dist) 存储在队列元素中，也可以使用队列大小技巧（在每一层开始前记录队列大小，恰好处理这么多个节点，然后递增层级计数器）。两种方法都会得到相同的结果。
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}克隆图
克隆图（LeetCode #133）会创建一个连通无向图的深层副本。请使用 BFS 和一个将原节点映射到克隆节点的哈希映射。第一次访问某个节点时，创建它的克隆节点并将其加入映射。在处理邻居时，查找或创建它们的克隆节点，并连接相应的边。哈希映射具有双重作用：既可以跟踪已访问节点，也可以将原节点映射到副本。
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]双向 BFS
双向 BFS同时从源节点和目标节点开始 BFS，并从两端每次扩展一层。当两个前沿相遇时，就找到了最短路径。对于大型图，这会将搜索空间从 O(b^d) 缩减为 O(2 * b^(d/2))，其中 b 是分支因子，d 是路径长度——对于包含大量词典的单词接龙这类连接非常密集的图，改进十分显著。
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'])) # 5加权图中的 0-1 BFS
0-1 BFS用于处理边权仅为 0 或 1 的图。请使用双端队列代替普通队列：对于权重为 1 的边（下一层），使用 `append` 添加到队尾；对于权重为 0 的边（同一层），添加到队首。这样可以在 O(V + E) 的时间内计算最短路径；当权重为二值时，它比迪杰斯特拉算法的 O((V+E) log V) 更快。这种方法常用于网格问题，其中某些移动免费，而其他移动的代价为 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]墙与门（多源 BFS）
墙与门会将每个空房间填充为它到最近门的距离。请使用多源 BFS：同时将所有门（值为 0）初始化到队列中，然后向外扩展。每个单元格的值设置为它第一次被到达时所在的层级。这个 O(mn) 的解决方案比从每个空房间分别运行 BFS 更高效，后者的复杂度为 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, 2蛇与梯子 BFS
蛇与梯子（LeetCode #909）是一个在数字网格上求最短路径的 BFS 问题。请将棋盘建模为无权图：从任意方格都可以掷出 1-6，并且可能落在会将您传送到其他位置的蛇或梯子上。BFS 可以找到最少的骰子投掷次数。关键难点是处理一维位置与二维棋盘坐标之间的转换，同时考虑行方向交替的蛇形布局。
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 复杂度与优化
BFS 的时间复杂度为O(V + E)，因为每个顶点只入队一次，并且每条边都会被检查常数次。空间复杂度为O(V)，用于存储已访问集合和队列。对于网格图，V = m*n 且 E = 4*m*n（每个单元格有 4 个邻居），因此网格上的 BFS 复杂度为 O(mn)。关键优化是：使用集合跟踪已访问节点（查找为 O(1)），而不是使用列表（查找为 O(n)）。在入队时标记已访问，而不是在出队时标记。
# 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')二进制矩阵中的最近 0
01 矩阵（LeetCode #542）用于求每个单元格到最近 0 的距离。从所有 0 同时开始执行多源 BFS，可以得到最优的 O(mn) 解决方案。将所有 0 单元格以距离 0 初始化到队列中，并将所有 1 单元格的距离设为无穷大。BFS 从 0 向外传播距离，在每个 1 单元格第一次被到达时设置其距离（可以保证这是最短距离）。
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]]快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中您学习了：无权图中用于查找最短路径的 BFS，以及用于还原路径的父节点跟踪；将单词接龙作为隐式图上 BFS 的典型应用；适用于大型图的双向 BFS；以及用于多个起点问题的多源 BFS。接下来，我们将应用 DFS 处理连通分量和泛洪填充。
常见问题解答
「BFS：最短路径与层序遍历」课时是免费的吗？
是的 — 「BFS：最短路径与层序遍历」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「BFS：最短路径与层序遍历」这节课中我会学到什么？
使用 BFS 查找无权图中的最短路径，逐层解决单词接龙，并使用哈希映射克隆图。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「BFS：最短路径与层序遍历」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 图的表示与遍历准备
- BFS：最短路径与层序遍历
- DFS：连通分量与洪水填充
- 有向图与无向图中的环检测