BFS遍历矩阵迷宫时陷入无限循环的解决方案_技术教程

bfs在矩阵迷宫中搜索路径时，若未标记已访问节点，会导致同一位置反复入队，引发队列持续增长、永不为空的死循环。关键在于引入访问标记机制，避免重复访问。

在您提供的代码中，BFS逻辑结构基本正确：从起点入队，逐层扩展上下左右四个方向的合法邻居，并通过 Box 节点的 parent 字段回溯路径。但核心缺陷在于缺少访问状态管理——程序未记录哪些坐标已被探索过，导致节点反复被重新加入队列。

例如，从 (0,0) 扩展到 (0,1) 后，当 (0,1) 出队时又会检查 (0,0)（左邻），而此时 (0,0) 仍满足 isFree() 条件（值为 0 且坐标合法），于是重新入队。如此往复，形成环路，队列无限膨胀。

✅ 正确做法是：每弹出一个节点（poll()）后，立即标记其坐标为“已访问”；后续所有邻居入队前，必须同时校验边界、可通行性和未访问状态。

推荐使用二维布尔数组 visited[][] 实现标记（也可复用原矩阵做原地标记，但需谨慎处理）：

public static void searchPath(int[][] maze, int startX, int startY, ArrayList path) {
    int rows = maze.length;
    int cols = maze[0].length;
    boolean[][] visited = new boolean[rows][cols]; // 新增访问标记数组
    Queue queue = new LinkedList<>(); // 避免静态变量，防止多线程/多次调用冲突
    queue.add(new Box(startX, startY, null));
    visited[startY][startX] = true; // 入队即标记

    while (!queue.isEmpty()) {
        Box p = queue.poll();

        if (maze[p.y][p.x] == 9) {
            System.out.println("Exit is reached!");
            getPath(p, maze, path);
            return;
        }

        // 四方向扩展（顺序无关紧要）
        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        for (int[] dir : directions) {
            int nx = p.x + dir[0];
            int ny = p.y + dir[1];
            if (isFree(maze, nx, ny) && !visited[ny][nx]) {
                visited[ny][nx] = true; // 入队前标记，防重复
                queue.add(new Box(nx, ny, p));
            }
        }
    }
    System.out.println("No path found.");
}

// isFree 保持不变，但注意：原实现中 maze[y][x] 的索引顺序需与实际矩阵维度一致（此处假设 maze[y][x] 正确）
public static boolean isFree(int[][] maze, int x, int y) {
    if (x >= 0 && x < maze[0].length && y >= 0 && y < maze.length) {
        int val = maze[y][x];
        return val == 0 || val == 2 || val == 9; // 仅允许通路、路径标记、终点
    }
    return false;
}

⚠️ 重要注意事项：

避免静态队列：原代码中 public static Queue q 是危险设计。静态变量跨调用持久化，易引发状态污染；应改为局部变量或通过参数传递。
索引一致性：maze[y][x] 表示第 y 行、第 x 列，需确保 maze 是 rows × cols 结构（即 maze.length 为行数，maze[0].length 为列数）。isFree() 中 maze[y][x] 的行列顺序必须与矩阵实际布局严格匹配。
标记时机：务必在 queue.add() 之前设置 visited[ny][nx] = true，否则在高并发或多分支场景下仍可能因竞态导致重复入队。
内存与性能：对大型迷宫，visited 数组是必要开销；若内存受限，可考虑将已访问位置在 maze 中临时设为 -1 等非法值（但需保证不影响 isFree() 判断逻辑）。

总结：BFS 的本质是层级遍历，其正确性依赖于每个节点仅被处理一次