Java实现BFS求解迷宫最短路径：从建模到回溯的完整指南

学过数据结构和算法的朋友应该都撞过迷宫题一个二维网格起点在左上角终点在右下角0代表可走的路1代表墙让你输出从起点到终点的最短路径。这类题在笔试和面试里出现频率相当高因为它在很小的代码量里同时考察了三样东西——图的建模、队列的使用、以及路径回溯。用 Java 写 BFS广度优先搜索解迷宫题本质上就是干这三件事。这篇文章我会把这道题完整拆开讲先讲怎么把迷宫建模成程序能处理的结构再讲 BFS 为什么是求最短路径的天然武器然后给出一份带详细注释的 Java 实现包括路径回溯的完整写法最后把我实际调试中踩过的坑和几个进阶方向一并交代。适合刚学完图论、准备系统刷题的人也适合想写得更稳健的实战派。1. 迷宫题到底在考什么为什么默认答案是 BFS1.1 迷宫的本质是无权图上的最短路径问题很多人在看到迷宫时只想到一条路走到底的深搜但换个角度想每个格子是一个节点相邻两个可通行的格子之间有一条边那整个迷宫就是一张图。从任意格子走到相邻格子代价都是 1 步所以这是一张无权图而题目求的最少步数就是无权图上的最短路径。BFS 在这类问题上是标准答案因为它有一个非常关键的特性第一次访问到某个节点时所走的路就是到该节点的最短路径。这个特性是 DFS 不具备的。DFS 找到一条通往终点的路径就结束了但这条路径可能是绕了远路的路径BFS 则是一层一层向外扩散终点第一次被弹出队列的那一刻必然走的是最短路径。生活化的类比就是向水面丢石子波纹一圈一圈往外推开波纹到达某块木板的那一刻就是石子落点离木板最近的距离。迷宫里的 BFS 就是模拟这种波纹扩张。1.2 为什么用 DFS 写迷宫容易出问题不是说 DFS 不能写迷宫而是它在求最短路径这个诉求下不占优势。如果你只是问有没有路到终点DFS 完全没问题但若问最少几步DFS 得把所有路径都走一遍才能比较出最短路那是灾难级的复杂度。更现实的问题是DFS 在 Java 里常用递归实现迷宫大了以后递归深度跟着边长走一个几百乘几百的迷宫就能把栈压垮直接抛StackOverflowError。BFS 就没有这个问题。它用的是队列没有递归不存在栈溢出风险空间复杂度最坏也就 O(M×N)M、N 分别是迷宫的行和列因为最多所有格子同时入队。这也是面试官更倾向让你写 BFS 的原因——稳、快、省心。2. 建模先行把迷宫翻译成程序的语言2.1 坐标系与二维数组的约定写代码之前先把坐标体系定清楚这一步通常被新手忽略但恰恰是后面所有代码正确性的基础。常规做法是用二维数组maze[x][y]表示格子x是行索引y是列索引映射到数学坐标系就是(x, y)坐标。数组里存的值按题目约定0代表空地可以走1代表墙。我把这个约定写成一个常量定义放在代码最前面避免在判断里直接写裸数字。起点和终点的表示我习惯用长度 2 的int[]数组{x, y}来装坐标。虽然每次新建一个小数组有些开销但胜在读起来直观刷题场景下完全够用。追求极致性能的可以改用一维索引index x * COLS y这个我放到第 5 章优化部分再说。迷宫定义我放在main外面作为静态常量这样 BFS 方法里直接引用不用把迷宫作为参数传来传去代码更干净。2.2 方向数组四行代码解决状态转移BFS 扩展节点时需要枚举当前格子的四个相邻格子。最朴素的做法是写四段重复逻辑左、右、上、下各处理一遍。代码能跑但显得很笨而且极易漏掉方向或写错索引。更好的做法是用方向数组// 四个方向右、下、左、上 private static final int[] DX {0, 1, 0, -1}; private static final int[] DY {1, 0, -1, 0};这里的逻辑是DX[i]和DY[i]组合就是第 i 个方向的行偏移和列偏移。向右行不变、列加 1即(0, 1)向下行加 1、列不变即(1, 0)。这样在 BFS 里只需要一个 for 循环就能把四个方向全部遍历完代码量瞬间减掉四分之三也方便以后把方向扩展成 8 个加上四个斜向。方向顺序本身不影响最短路径的步数只会影响多条等长路径里具体选哪一条。比如先向右再向下路径就会偏向先往右走反过来则先往下。调试时如果发现路径形状和预期不一致先检查方向数组的顺序不用怀疑算法有问题。3. BFS 求最短路径的核心原理3.1 队列、分层与波前推进BFS 的代码很简单但很多初学者只是背下了模板没理解队列在这里到底在做什么。BFS 的核心机制是队列保证节点按离起点的距离严格递增地被访问。一开始队列里只有起点。第一轮从队列取出起点把它的所有邻居入队第二轮取出的节点全是距离起点 1 的节点再把它们的邻居入队去掉已经访问过的第三轮取出的全是距离起点 2 的节点。队列像一条传送带把节点按波纹圈层的顺序送到你面前。我习惯把这个过程想成一圈一圈地蔓延第 0 圈起点 (0,0) 第 1 圈所有能一步到达的格子 第 2 圈所有能两步到达的格子 …… 第 k 圈所有能 k 步到达的格子终点第一次出现在队列中时或者说第一次被弹出时它所在的圈数就是最短距离。这个第 k 圈的思想直接对应着 BFS 里距离分层的本质理解它之后你再看任何 BFS 代码都会觉得顺眼很多。3.2 visited 数组标记时机是关键BFS 里必须有访问标记否则会出现两个问题一是同一个格子被反复入队队列无限膨胀二是有可能陷入死循环比如两个相邻空地互相入队。解决办法是准备一个二维布尔数组visited[x][y]。但这里藏着一个新手最常见的错误到底是入队时标记还是出队时标记答案是入队时标记。原因很简单如果一个节点已经被加入队列它的信息就已经在待处理列表里了不应该再被第二次加入。如果只在出队时标记那么在它还没出队之前其他邻居完全可能再次发现它并再次把它入队同一个格子被入队两次甚至多次队列里出现大量冗余节点。在极端情况下还会导致某些本应更短的路径被覆盖记录进而影响路径回溯的正确性。想象一下排队办业务你取号时就被系统登记了而不是轮到你办业务时才登记。别人再加号时看到你的号已经在系统里就不会重复给你发号了。3.3 路径回溯从终点走回起点求最短路径不能只求步数还要把具体的路径输出出来。最常用的做法是维护一个prev前驱数组每当节点(nx, ny)第一次被访问时记录它是由哪个格子走过来的也就是prev[nx][ny] (x, y)。因为每个格子只被访问一次它的前驱也只会被记录一次而且这个前驱必然来自最短路径BFS 分层特性保证的。最终从终点出发顺着prev一路回退就能走回起点再把这一串节点反转得到的就是从起点到终点的正序路径。这一节没有太复杂的理论但它是整个题里最容易被写崩的地方——具体怎么用代码实现回溯我放在下面完整代码里讲。4. Java 完整实现附逐段注释4.1 数据结构选型先聊选型。队列我用的LinkedList它实现了Queue接口offer和poll方法语义清晰。刷题时也可以用ArrayDeque它底层是循环数组元素操作更快但真题讲解里LinkedList更常见两种我都写过这里先用LinkedList第 5 章再展开性能对比。坐标存储用int[]数组{x, y}两个元素。虽然每次入队都要new一个数组但写起来直白适合先跑通逻辑。路径回溯的prev我用了一个三维数组int[][][] prev前两个维度是坐标第三维存的是前驱坐标数组。这种写法在 Java 里很直观但也有人用HashMapInteger, int[]来压缩空间后面优化部分再说。访问标记用boolean[][] visited迷宫多大它就多大加上prev总的空间开销是 O(M×N)完全可接受。4.2 完整代码详细注释下面这份代码我觉得是目前能给出的比较平衡的方案注释详细但不啰嗦结构清晰直接可运行。import java.util.*; public class MazeBFS { // 迷宫定义 // 约定0 表示可通行1 表示墙壁 private static final int[][] MAZE { {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0} }; private static final int ROWS MAZE.length; private static final int COLS MAZE[0].length; // 方向数组右、下、左、上 private static final int[] DX {0, 1, 0, -1}; private static final int[] DY {1, 0, -1, 0}; public static void main(String[] args) { int[] start {0, 0}; int[] end {4, 4}; Listint[] path bfs(start, end); if (path null) { System.out.println(起点到终点没有通路); return; } System.out.println(最短路径步数 (path.size() - 1)); System.out.println(路径坐标); for (int[] p : path) { System.out.println( ( p[0] , p[1] )); } printMazeWithPath(path); } /** * BFS 搜索最短路径 * * param start 起点坐标 {x, y} * param end 终点坐标 {x, y} * return 从起点到终点的坐标列表含起点和终点无解返回 null */ public static Listint[] bfs(int[] start, int[] end) { // visited[x][y] 标记格子是否已被加入队列防止重复访问 boolean[][] visited new boolean[ROWS][COLS]; // prev[x][y] 记录格子 (x,y) 的前驱坐标用于最后还原路径 int[][][] prev new int[ROWS][COLS][]; // 队列存放待访问的坐标 Queueint[] queue new LinkedList(); // 起点入队并标记访问 queue.offer(start); visited[start[0]][start[1]] true; while (!queue.isEmpty()) { int[] cur queue.poll(); int x cur[0]; int y cur[1]; // 当前节点就是终点直接回溯路径 if (x end[0] y end[1]) { return buildPath(prev, start, end); } // 遍历四个方向 for (int i 0; i 4; i) { int nx x DX[i]; int ny y DY[i]; // 三个条件缺一不可不越界、不是墙、未访问 if (nx 0 nx ROWS ny 0 ny COLS MAZE[nx][ny] 0 !visited[nx][ny]) { // 入队时立即标记访问而不是出队时标记 visited[nx][ny] true; // 记录前驱格子 (nx, ny) 是从 (x, y) 走过来的 prev[nx][ny] cur; queue.offer(new int[]{nx, ny}); } } } // 队列为空且未到达终点说明所有可达节点都遍历完了 return null; } /** * 从终点顺着 prev 回溯到起点反转后得到正序路径 */ private static Listint[] buildPath(int[][][] prev, int[] start, int[] end) { Listint[] path new ArrayList(); int[] cur end; while (true) { path.add(cur); if (cur[0] start[0] cur[1] start[1]) { break; } cur prev[cur[0]][cur[1]]; // 向前回退一步 } Collections.reverse(path); // 现在是逆序反转成正序 return path; } /** * 把迷宫和路径画出来方便肉眼验证 */ private static void printMazeWithPath(Listint[] path) { char[][] grid new char[ROWS][COLS]; for (int i 0; i ROWS; i) { for (int j 0; j COLS; j) { grid[i][j] MAZE[i][j] 1 ? # : .; } } for (int[] p : path) { grid[p[0]][p[1]] *; } for (int i 0; i ROWS; i) { for (int j 0; j COLS; j) { System.out.print(grid[i][j] ); } System.out.println(); } } }4.3 运行效果与复杂度分析这段代码跑起来输出大致是最短路径步数12 路径坐标 (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (1, 2) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) (3, 4) (4, 4) * # * * * * # * # * * * * # * * # # # * * * * * *这个迷宫设计的比较巧唯一的通路绕了很大一圈正好能看出 BFS 找的是真正最短的那条而不是看起来像能走就冲的路。复杂度方面BFS 每个格子最多入队一次、出队一次每个格子又最多扩展 4 个方向所以时间复杂度是 O(M×N)。空间上visited和prev都是 O(M×N)队列最坏也 O(M×N)总空间 O(M×N)。这个复杂度对迷宫题来说是理论最优的因为你至少要看一眼每个格子不可能更少。5. 避坑指南与调试心得5.1 四个经典错误第一个坑就是前面反复强调的出队时才标记 visited。这是我见到的最高频错误后果是同一个节点反复入队队列膨胀甚至可能导致路径回溯时prev被后到的非最短路径覆盖最终输出的路径不是最短的。第二个坑是起点没有标记 visited。起点一旦不标记第一轮扩展邻居时如果有邻居能走回起点就会把起点再次入队形成一条 2 步的回环。虽然最终代价可能不高但整个 BFS 的最短性就被破坏了调试起来非常隐蔽。第三个坑是边界检查漏掉一边。很多初学者写了nx 0和ny 0却忘了nx ROWS和ny COLS数组下标越界直接ArrayIndexOutOfBoundsException。这种错误特别好排查报错信息会定位到行但也很容易在自己的代码里反复犯。第四个坑是路径回溯时空指针。buildPath里如果prev[cur[0]][cur[1]]是null说明某个节点的前驱没被正确记录。常见原因是访问标记的时机和prev赋值的位置不一致比如标记了 visited 但没赋 prev或者赋值在判断条件外面。我建议把三行代码写成固定搭配永远一起出现visited[nx][ny] true; prev[nx][ny] cur; queue.offer(new int[]{nx, ny});这三个动作是一个整体缺一个都会出问题。5.2 可视化调试法迷宫题有个得天独厚的调试优势它是二维的可以直接打印出来。我在printMazeWithPath里把墙画成#、空地画成.、路径画成*一眼就能看出路径是否合理。如果路径不对先把visited数组也打印出来看看每个格子第一次被访问的层数是不是递增的。具体做法是在访问数组里记录距离int[][] dist new int[ROWS][COLS]; // 入队邻居时 dist[nx][ny] dist[x][y] 1;然后打印dist矩阵你会清楚地看到波纹扩散的痕迹。如果某个格子距离值很奇怪比如突然出现跳跃那多半是标记时机或方向数组编写有误。我调试时还有个习惯把队列的大小打印出来。如果队列大小在 BFS 过程中不降反升、甚至越来越大说明有节点被重复入队了先检查 visited 相关的逻辑这个信号往往比看路径更快定位问题。5.3 性能优化小技巧刷题和做项目不同性能优化的优先级要看题目规模。如果迷宫是 1000×1000 这种级别几个优化点值得考虑。第一个优化是用坐标索引代替int[]数组。把坐标编码成整数idx x * COLS y入队出队的对象从数组变成基本类型intJava 的自动装箱在这里不会发生因为LinkedListInteger里的Integer还是会装箱但ArrayDequeInteger配合基本类型操作内存开销和 GC 压力都小很多。prev数组也可以从三维缩成一维int[] prev存前驱的索引。第二个优化是使用ArrayDeque替代LinkedList。LinkedList每个节点都有额外的指针开销ArrayDeque是循环数组缓存友好性更好。实测在百万级节点上差别明显但对 5×5 的演示迷宫几乎没有区别。第三个优化是提前返回。虽然我在演示代码里已经是终点出队时返回了但更精细的做法是在入队时就检查nx、ny是否是终点是的话立刻回溯路径可以少一轮循环。这个优化代码上只需要多加两个判断if (nx end[0] ny end[1]) { prev[nx][ny] cur; return buildPath(prev, start, end); }注意这里要先把prev赋值好再返回否则回溯会断链。6. 从一趟 BFS 延伸出去的进阶玩法6.1 从最短路径到最短距离dist 数组的妙用有时候题目只要求输出最短步数不需要路径。那prev数组可以省掉换成dist数组记录每个格子的距离。逻辑几乎一样唯一区别是在入队邻居时更新距离dist[nx][ny] dist[x][y] 1;还有一个更省空间的技巧直接用visited存步数。把所有格子初始化为 -1 表示未访问起点为 0入队邻居时步数加一。这样既充当了访问标记又记录了距离一次遍历同时拿到最短步数int[][] steps new int[ROWS][COLS]; for (int i 0; i ROWS; i) { Arrays.fill(steps[i], -1); } // 入队邻居时 steps[nx][ny] steps[x][y] 1;6.2 加权迷宫与 0-1 BFS如果迷宫里的移动代价不再恒为 1而是某些格子走过去要花不同的代价BFS 就不适用了。比如每个格子有一个体力消耗值走进去会消耗不同体力。此时需要 Dijkstra 算法它用优先队列代替普通队列每次都选当前代价最小的节点扩展。如果移动代价只有两种比如普通格子代价 1传送门格子代价 0那可以用更轻量的0-1 BFS。它使用双向队列Deque代价为 0 的边从队头插入代价为 1 的边从队尾插入。这样不需要建堆时间复杂度仍然是 O(M×N)比 Dijkstra 更快。它的原理本质上还是利用 BFS 的分层思想只是把层与层之间的边界用 0 代价压缩了。6.3 双向 BFS 与多终点当迷宫很大、起点和终点位置相距很远时可以试试双向 BFS同时从起点和终点出发各做一次 BFS两边的波纹相遇时路径长度就是两边各自步数之和。这种技巧能显著减少搜索空间。迷宫越大收益越明显。如果题目有多个终点比如多个出口也不用慌。BFS 天然支持多终点场景方法就是多源 BFS把所有出口全部初始入队让波纹从多个出口同时扩散。谁先到达起点对应的出口就是最近的。这个思想在很多图论题里都有用武之地比如找离所有商店最近的小区地图上离所有加油站最近的位置等等。最后说一个我在多次实战里的体会刷迷宫题不要只盯着写出来跑通这个目标。把visited的标记时机、prev的回溯逻辑、方向数组的写法这三件事想透彻了BFS 这一套就真正内化了后面不管遇到岛屿数量、单词接龙、还是二叉树层级遍历都会发现只是同一个套路换了个壳。尤其是prev回溯学会了就不只是会解迷宫以后遇到任何求具体路径的问题比如寻路系统、拓扑排序输出顺序都能直接复用这套思路。从我会用 BFS 之后凡是见到最短路三个字第一反应已经不是写代码那么简单了而是先判断图的类型无权、有权、还是 0/1 权然后决定上哪种搜索策略。这一步想清楚了代码反而成了最不花时间的那部分。