最近在做项目时遇到一个蛮有意思的需求在迷宫中找从起点到终点的最短路径。原本想着用深度优先搜索一路莽过去结果发下跑出来的路径绕来绕去完全不是最短路线。换了广度优先搜索BFS之后问题立刻清爽了——它天生就是为“最短路径”设计的。这篇就把我在“BFS走迷宫”这个经典算法题上的完整思路、代码实现和实战经验整理出来适合刚开始接触搜索算法、或者已经在用但想把细节彻底吃透的朋友。先交代一下我面对的具体场景一张 40×40 的二维网格迷宫格子分为可通行空地、障碍墙、起点和终点需要找出一条从起点到终点的最短路径路径长度按格子数计算。这个规模不算大但也足够让我在选型上踩一轮坑。1. 为什么选BFS而不是DFS两道迷宫题的选型对比很多入门资料会把 DFS 和 BFS 放在一起讲初学者也容易混淆。做完这个项目后我的体会是DFS 适合“判断有没有路能到终点”BFS 适合“找到最短的那条路”。两者的核心差别在于搜索时的扩展顺序。1.1 DFS 的贪快逻辑为何不适合迷宫最短路径DFS 的核心思路是“一条路走到黑”不行就回头。它用一个栈或者直接递归保存待访问节点每次尽量往深处走。这种策略在迷宫规模小、只需要“找一条路”的时候效率很高代码也非常短十几行就能写完。但它的致命缺点是它找到的第一条路径完全取决于邻居遍历顺序。假设我按“上右下左”的顺序扩展方向DFS 可能优先往上方探结果一头扎进一条绕远路的死走廊来回回溯了好多次才出来。哪怕最终找到了出口这条路也可能是全长 137 步的歪路而实际最短路径只有 61 步。还有一个隐藏问题DFS 的实现如果写得不好很容易在递归层数太深时爆栈。迷宫一大递归调用成千上万层运行环境直接报错。1.2 BFS 的层级扩展特性带来的天然优势BFS 的做法是“一层一层地扫”。从起点开始先看所有 1 步能到达的格子再看 2 步能到达的格子以此类推。这个特性决定了它有一个非常重要、写在教科书里的性质当某个节点第一次被访问到时从起点到它的路径就一定是最短的。这其实是一种非常朴素的思路如果从起点到目标需要 k 步那么在第 k 轮扫描过程中BFS 一定会在这一轮覆盖到它而且所有更短的位置都在前面几轮里被扫过并标记过了。第 k 轮是“第一次触及”这个目标的轮次所以不存在更短路径。我第一次在项目中跑通 BFS 迷宫求解时看到输出路径长度从 DFS 的 137 步降到 61 步那种“啊原来选对算法这么重要”的感觉非常直观。这也是为什么要单开一章对比二者因为选型对了后面的工作都会顺很多。2. BFS最短路径的底层依据队列与层级扩展开的数学直觉不少人在学 BFS 时直接把代码背下来了但没理解为什么它一定能保证最短。其实把这个“为什么”想通了代码怎么写手到擒来。2.1 队列为什么是BFS的天然搭档BFS 的扩展顺序是“先来先服务”谁先被发现谁就先被继续扩展。这句话翻译一下就是一个先进先出的结构——队列。队列保证了“当前层的所有格子一定先于下一层的格子被处理”。举个例子帮助理解排队打饭时先到的人先打饭。假设起点是第一个人它“喊”来了周围 4 个邻居这 4 个邻居排到队尾起点打完饭出队后队伍最前面的邻居开始“喊”它的邻居。这个过程天然地会让所有离起点距离为 1 的格子先被处理完然后才轮到距离为 2 的。如果换成一个栈也就是让后到的先处理那整个搜索顺序就会变成一条道钻到底层级感完全消失最短性也随之消失。2.2 为什么“第一次访问即最短”在网格迷宫中可靠在网格迷宫中每一步的代价是 1起点到每个格子的距离等于经历的格子数减 1。BFS 按层扩展时第 d 轮处理的是距离为 d 的格子。当某个格子第一次被扫描到并加入队列时它所在的层数就是它的最短距离之后就算再被其他邻居发现层数也不可能比第一次更小。写代码时可以用一个 visited 数组记录“是否已经被访问”用一张 dist 表记录“从起点到这个格子的步数”。一旦格子被标记为 visited就不再去更新它的距离。这个技巧既保证了最短性也避免了重复入队引起的死循环和资源浪费。为了严谨我当时在代码里做了个小实验把某个格子允许重复访问结果在 40×40 的随机地图上队列里瞬间涌入了大量重复节点解还是能解出来但时间和空间开销翻了近十倍而且后续路径回溯时会绕晕。所以这个“第一次访问即锁定距离”的规则不仅是对的还是性能的关键。3. 可直接运行的BFS迷宫求解Python实现与关键注释理论说完了接下来是能直接抄走跑的代码。我用 Python 写了完整版本代码结构分为三步地图读取与解析、BFS 搜索、路径回溯与输出。配合注释新手也能很轻松地对照着理解每一步的作用。3.1 地图矩阵的数据结构设计与解析过程首先需要定义迷宫地图的表示方式。我用的是典型的二维网格每个格子的取值含义如下值含义0可通行空地1障碍墙2起点3终点这种数字表示的好处是既方便程序判读又能在调试时用文本方式打印出来非常直观。我用一个纯文本文件来存地图每一行是一串数字读进来就是一个嵌套列表或者说二维矩阵。def load_maze(filename): with open(filename, r, encodingutf-8) as f: raw_lines [line.strip() for line in f if line.strip() ! ] maze [] start None end None for i, line in enumerate(raw_lines): row [] for j, ch in enumerate(line.split()): cell int(ch) row.append(cell) if cell 2: start (i, j) elif cell 3: end (i, j) maze.append(row) return maze, start, end这段代码里有个细节值得注意起点和终点我都在解析过程中顺便找出来了不用事后二次遍历矩阵省了一点时间。对于大地图来说这种“一次解析顺带提取关键信息”的习惯很实用。3.2 BFS主流程队列初始化、邻居扩展与访问标记核心的 BFS 搜索逻辑不长但每一行都需要对它为什么这么写有清晰认知。from collections import deque def bfs_shortest_path(maze, start, end): rows len(maze) cols len(maze[0]) visited [[False] * cols for _ in range(rows)] prev [[None] * cols for _ in range(rows)] queue deque() queue.append(start) visited[start[0]][start[1]] True # 四个方向的移动向量上、下、左、右 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: cur queue.popleft() r, c cur if cur end: break for dr, dc in directions: nr, nc r dr, c dc # 检查边界同时检查是墙还是空地 if 0 nr rows and 0 nc cols: if not visited[nr][nc] and maze[nr][nc] ! 1: visited[nr][nc] True prev[nr][nc] cur queue.append((nr, nc)) return prev这里有三个容易踩的细节。第一个visited是在节点入队时标记不是出队时标记。如果等出队才标记同一个节点可能被多个邻居在入队前重复加入队列队列膨胀且后续回溯路径时会出现分叉指向同一个节点的问题。第二个prev二维数组全程记录了“我是被谁发现的”。这有点像职场里的“推荐人制度”每个新员工都知道是谁把自己招进来的最终要追溯入职链条时只要逐级往上问就行。第三个边界检查一定要在最前面做。很多初学者喜欢先把邻居节点算出来然后直接用越界的索引去访问数组立刻报 IndexError。先判断边界再访问是网格类算法里的通用好习惯。3.3 从prev表回溯路径终点逆推起点的完整过程prev表记录完成之后从终点倒推回起点的过程其实就是一个简单的链表回溯def reconstruct_path(prev, start, end): if prev[end[0]][end[1]] is None: return None # 说明终点从未被访问即无通路 path [] cur end while cur ! start: path.append(cur) cur prev[cur[0]][cur[1]] path.append(start) path.reverse() return path这段代码里有个我刚开始经常犯的错忘了判断终点是否有prev值。如果地图根本没有通路prev[end]就一直是None直接回溯会陷入死循环或者返回错误路径。先判断再回溯非常关键。path里存的是从起点到终点经过的所有格子坐标。如果你只需要步数直接看len(path) - 1就行。因为路径包括起点本身所以步数要减一。3.4 理解“入队即标记”为何是性能关键我在第 3.2 节已经提到visited要在入队时立即标记。这里再展开说一下性能上的实际影响。假设迷宫里有一个宽阔的开放区域中间有一个格子被 6 个邻居同时扫描到。如果入队时不标记这 6 个邻居都会把这个格子当成“未访问”并各自把它加进队列。这样同一个格子就可能在队列里出现 6 次。在更大的地图里这个重复系数会成倍放大队列长度暴涨内存占用也随之暴涨。而“入队即标记”是一个巧妙的剪枝一个格子一旦被排进队列即使后来又被其他邻居发现也不会再次入队。这样每个格子至多入队一次整体复杂度就能稳定在 O(rows * cols) 级别。这个道理放在多源 BFS、 Dijkstra 等复杂算法里也完全适用值得养成习惯。4. 动起来的搜索过程用可视化和动画把BFS“看”明白算法光跑通还不够如果能把它怎么工作的过程“看”到理解就会加深不少。我后来给 BFS 做了简单可视化效果非常直观。4.1 基于matplotlib的分步绘制方案可视化策略其实不复杂。我用了 matplotlib把整个迷宫渲染成色块墙是深灰色空地是浅灰色已访问的格子慢慢变成蓝色当前正在扩展的格子高亮成黄色起点标记成绿色终点标记成红色。核心思路是每一步 BFS 循环后都重新绘制一次当前状态然后调用plt.pause(0.05)让画面停顿一小段时间形成动态观察效果。如果你不想实时推演也可以使用plt.savefig把每一帧存成图片最后再把几十张图片合并成 GIF。import matplotlib.pyplot as plt from matplotlib.colors import ListedColormap def visualize_bfs(maze, start, end, prev): rows len(maze) cols len(maze[0]) # 构造显示用矩阵 display [[0 for _ in range(cols)] for _ in range(rows)] cmap ListedColormap([white, black, green, red, yellow, blue]) fig, ax plt.subplots(figsize(6, 6)) queue deque([start]) visited [[False]*cols for _ in range(rows)] visited[start[0]][start[1]] True directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: cur queue.popleft() r, c cur # 渲染当前状态 display_map [[maze[i][j] if maze[i][j] ! 0 else (3 if (i, j) start else 4 if (i, j) end else 5 if visited[i][j] else 0) for j in range(cols)] for i in range(rows)] ax.imshow(display_map, cmapcmap, vmin0, vmax5) ax.set_title(fCurrent: ({r}, {c})) plt.pause(0.05) if cur end: break for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols: if not visited[nr][nc] and maze[nr][nc] ! 1: visited[nr][nc] True prev[nr][nc] cur queue.append((nr, nc))上面这段代码我故意简化了色彩映射逻辑核心是让你看到“队列弹出节点→感染邻居→邻居变色→继续弹出”的循环过程。跑一次之后你会非常直观地感受到 BFS 的“扩散”效果颜色从起点像水波一样一圈圈向外晕开而不是像 DFS 那样沿着一个方向冲出去。4.2 终端文本动画没有GUI环境也能看BFS过程如果不装 matplotlib 或者身处纯终端环境也有一个低成本方案每轮搜索后清屏重新打印一次迷宫地图把当前已访问的格子用特定符号标出来。下面这段代码展示了一个最小实现的思路import os def print_maze_state(maze, visited, cur): os.system(cls if os.name nt else clear) symbols {0: ., 1: #, 2: S, 3: E} for i in range(len(maze)): line for j in range(len(maze[i])): if (i, j) cur: line * elif visited[i][j]: line o else: line symbols.get(maze[i][j], ?) print(line)基于这段代码在主循环中适当调用即可看到搜索的推进过程。终端动画虽然简陋但优势在于零依赖、随处可跑尤其适合写技术博客时放在文字稿里描述 BFS 行为。4.3 从动画中总结出的观察层级扩散的全过程我盯着动画看了十几遍之后对 BFS 的理解完全不一样了。有几个现象印象特别深刻第一访问区域是呈“菱形”或“圆角方形”扩散的因为每一步只能走上下左右四个方向所以扩散的边界从几何上看会逐步形成轴对齐的多边形。第二最早访问到的终点一定是“最短”的。动画里当它首次被染色时你甚至可以从染色波的节奏推断出路径长度——第 k 波到达终点时最短路径就是 k。第三如果迷宫里有两个终点同时存在BFS 先扫到哪一个取决于哪条路径更短以及队列中谁先出队。这就引出了一个多目标问题在多个出口下BFS 找到的只是一个花落谁家的问题具体谁先被扫到谁就是最近的出口。这些观察不仅对迷宫走法有帮助对理解“多源 BFS”“扩散模型”都很有启发。5. 实战中躲不开的边界问题死地图、超大迷宫与三维扩展跑通基本流程只是第一步。真正在实际项目里用还会遇到不少让人头疼的边界情况我把它们单独拎出来聊聊。5.1 通路根本不存在时如何优雅地处理无解地图最直接的情况是迷宫本身没有从起点到终点的通路。BFS 会老老实实遍历所有可达格子然后队列空了也没遇到终点。这种情况下reconstruct_path里判断prev[end] is None的逻辑就会起到保护作用。返回None后调用方可以打印“无通路”而不是继续回溯报错。另外有一点值得注意如果地图中存在“孤岛区域”——也就是被墙完全包围的空地——BFS 也会把这些区域全部扫描并标记为 visited。这在搜索时间上是白费的。如果你事先知道地图里可能有大量孤岛可以提前做一次“起点可达区域”的预计算把没必要搜的孤岛区域过滤掉。当然大多数迷宫规模下这点开销可以忽略。5.2 起点等于终点、多终点等特殊输入的防御性处理有次测试同事随手给了张起点和终点坐标重合的地图我当时的程序直接回溯路径只返回了一个格子严格来说没问题。但如果你判断“是否到达终点”的代码写得有问题可能起点还没入队就被判定为终点了输出结果就会怪异。建议在解析地图后对起点和终点做一个显式的合法性校验if start end: print(起点与终点重合) return [start]多终点的情况也值得考虑。如果地图里有多个值为 3 的格子按我之前的解析逻辑end变量只会保存最后遇到的那一个。这很可能不是离起点最近的那个。如果业务上要求“哪个近去哪个”你就得在 BFS 过程中一旦遇到任意一个值为 3 的格子就立即终止而不是提前固定唯一终点。多花几行代码能避免很多误解。5.3 处理超大迷宫时的双向BFS优化思路40×40 对 BFS 来说毫无压力但如果你遇到 1000×1000 甚至更大规模的网格单源 BFS 的搜索面积会变得十分可观。一个很经典的优化思路是“双向 BFS”。双向 BFS 的核心同时从起点和终点开始做 BFS两边各有一个 visited 集合和队列。每轮扩展“当前队列较小的一侧”当发现某个格子已经被另一侧访问到时说明两边相遇了路径就找到了。为什么它快因为 BFS 的访问区域像水波一样扩散单源扩散到相遇可能需要扫过的面积是正比于距离平方的双向扩散时两边各扫一半距离面积大约是小一半的距离平方总和远小于单向整个圆的面积。对于超大型迷宫这是一个量级上的性能提升。def bidirectional_bfs(maze, start, end): if start end: return [start] rows, cols len(maze), len(maze[0]) visited_start {start} visited_end {end} prev_start {start: None} prev_end {end: None} queue_start deque([start]) queue_end deque([end]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue_start and queue_end: # 扩展起点侧 for _ in range(len(queue_start)): cur queue_start.popleft() r, c cur for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and maze[nr][nc] ! 1: node (nr, nc) if node not in visited_start: visited_start.add(node) prev_start[node] cur if node in visited_end: # 相遇了拼接路径 return merge_path(prev_start, prev_end, node) queue_start.append(node) # 扩展终点侧 for _ in range(len(queue_end)): cur queue_end.popleft() r, c cur for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and maze[nr][nc] ! 1: node (nr, nc) if node not in visited_end: visited_end.add(node) prev_end[node] cur if node in visited_start: return merge_path(prev_start, prev_end, node) queue_end.append(node) return None双向 BFS 实现时要特别小心“每次扩展一层”的逻辑不能像普通 BFS 那样随便弹一个就扩一个否则两边扩展速度不一致会失去“同时扩散”的意义。上面用的是for _ in range(len(queue_start))这种层级扩展写法每一轮只扩散一层能保证两侧的搜索深度同步推进。5.4 三维迷宫的扩展可能性如果是三维迷宫格子从 (r, c) 变成 (r, c, z)方向从 4 个变成 6 个上下左右前后。核心 BFS 逻辑几乎不用改只需要两处调整一是邻居生成扩展出第三个维度的增量二是边界条件判断从二维变成三维。我自己在另一个项目里试过三维 BFS 寻路效果依然很稳定。这种“换个维度代码还能复用”的感觉很奇妙也从侧面说明算法本质和维度关系不大核心还是“层级扩展 队列 首次访问标记”这一套。三维场景下唯一要多留意的还是内存visited 数组从二维矩阵变成三维数组后体积会随 z 轴线性增加。如果地图规模很大可以考虑用字典存储已访问节点而不是预分配完整三维数组。6. 写在最后的人个经验这次做 BFS 走迷宫最大的收获不是背熟了某个模板而是真正体会到了“数据结构的选择如何决定算法行为”这件事。队列看起来平平无奇但正是这个先进先出的约束让 BFS 拥有了“逐层推进”这种保证最优的搜索顺序。很多时候我们觉得算法难其实是没把数据结构的技术选型和搜索策略之间的关联想透。如果你也在学 BFS我特别建议动手做几件事第一亲手把代码从零写一遍不要抄一边写一边想“为什么这里要标记 visited”“为什么这里用队列”。第二给迷宫加可视化和动画让搜索过程动起来那种“水波一圈圈扩散”的感觉会让你记住 BFS 的核心特性。第三去尝试一下无解地图、超大迷宫、三维迷宫这些边界场景实战里的坑往往比理论里的结论更值钱。最后送一个小技巧调试 BFS 时如果发现路径不对先别急着打一堆日志可以把 prev 表打印出来看看每个格子的“推荐人”是否合理路径回溯链条是否连贯基本一眼就能看出问题出在哪个环节。这套方法论不只在走迷宫里有用在很多图搜索相关的项目复盘里也一样管用。