在多维矩阵执行BFS遇循环引用无限循环，如何回溯获取路径？

你的代码里导致回溯无限循环的核心问题是parent数组的赋值逻辑完全搞反了，加上几个关键逻辑错误，下面逐个修正：

1. 核心错误：parent数组存储方向颠倒 #

你当前写的parent[current.getX()][current.getY()] = neighbor;，是把当前节点的父节点设成了邻居，完全搞反了逻辑——正确的应该是邻居节点的父节点是当前节点，也就是parent[neighbor.getX()][neighbor.getY()] = current;。

2. 目标节点的错误赋值 #

当current.equals(button)时，你错误地给parent[current.getX()][current.getY()] = previous;，这会覆盖掉当前节点的真实父节点（previous是上一次循环的current，并非当前节点的父节点），直接删掉这行即可。

3. visited集合的效率问题 #

用Queue<Cell>做visited集合，contains()方法是O(n)时间复杂度，效率极低且易出错，换成boolean[][] visited二维数组，直接通过坐标判断是否访问过，效率更高。

4. 移除冗余的previous变量 #

代码里的previous变量逻辑混乱，对路径回溯没有帮助，直接删除即可。

修复后的完整BFS代码 #

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {
    public List<Cell> breadthFirstSearch(Cell bot, Cell button, Fire fire, Ship ship) {
        int size = ship.getSize();
        // 二维数组记录访问状态，效率更高
        boolean[][] visited = new boolean[size][size];
        // parent数组：parent[x][y] 表示(x,y)节点的父节点，用于回溯路径
        Cell[][] parent = new Cell[size][size];
        Queue<Cell> queue = new LinkedList<>();

        // 初始化起点
        queue.add(bot);
        visited[bot.getX()][bot.getY()] = true;
        parent[bot.getX()][bot.getY()] = null;

        while (!queue.isEmpty()) {
            Cell current = queue.poll();
            System.out.println("当前遍历节点: " + current.toString());

            // 找到目标节点，开始回溯路径
            if (current.equals(button)) {
                List<Cell> path = new ArrayList<>();
                Cell node = current;
                while (node != null) {
                    path.add(node);
                    node = parent[node.getX()][node.getY()];
                    System.out.print("回溯节点: " + (node != null ? node.toString() : "null"));
                }
                // 反转得到从起点到终点的路径
                java.util.Collections.reverse(path);
                return path;
            }

            // 遍历当前节点的所有邻居
            for (Cell neighbor : getBotNeighbors(current)) {
                int nx = neighbor.getX();
                int ny = neighbor.getY();
                // 检查邻居是否合法：未燃烧、可通行、未被访问
                if (!ship.isBurning(nx, ny) && neighbor.isOpenCell(ship) && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(neighbor);
                    // 关键：设置邻居的父节点为当前节点
                    parent[nx][ny] = current;
                }
            }
            System.out.println();
        }
        // 无路径返回空列表
        return new ArrayList<>();
    }

    // 实现邻居获取逻辑（需添加边界检查）
    private List<Cell> getBotNeighbors(Cell current) {
        List<Cell> neighbors = new ArrayList<>();
        int x = current.getX();
        int y = current.getY();
        // 上下左右四个方向，需根据网格边界过滤无效坐标
        neighbors.add(new Cell(x - 1, y));
        neighbors.add(new Cell(x + 1, y));
        neighbors.add(new Cell(x, y - 1));
        neighbors.add(new Cell(x, y + 1));
        return neighbors;
    }
}

// 补充Cell类（必须重写equals和hashCode）
class Cell {
    private int x;
    private int y;

    public Cell(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    // 重写equals确保坐标匹配时返回true
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Cell cell = (Cell) obj;
        return x == cell.x && y == cell.y;
    }

    @Override
    public int hashCode() {
        return java.util.Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return "Cell{" + "x=" + x + ", y=" + y + '}';
    }
}

// 占位Ship和Fire类（根据实际实现调整）
class Ship {
    public int getSize() {
        return 5; // 对应示例5x5网格
    }

    public boolean isBurning(int x, int y) {
        return false; // 示例默认无燃烧区域
    }
}

class Fire {}

额外注意事项 #

• 必须确保Cell类重写equals和hashCode方法，否则current.equals(button)会比较对象内存地址，永远返回false。
• getBotNeighbors方法要添加边界检查，避免生成超出网格范围的无效坐标。

内容的提问来源于stack exchange，提问作者saanyay