BFS没有返回路径

Question

我试图在给定起点和终点的2d数组上实现BFS。我尝试在网格上给我的函数两个点，但它返回一个空数组，这意味着没有路径。

有人能指出我错在哪里，如果可能的话，帮助我纠正我的错误吗?谢谢。

public Point[] bfs2(Point start, Point end) {
    boolean[][] visited = new boolean[50][50];
    for (int i = 0; i < visited.length; i++)
        for(int j = 0; j < visited.length; j++)
            visited[i][j] = false;
    visited[start.getX()][start.getY()] = true;
    LinkedList<Point> path = new LinkedList<>();
    Queue<Point> q = new LinkedList<>();
    q.add(start);
    while (!q.isEmpty()) {
        Point next = q.remove(); //i think the error is here
        Point[] neighbours = next.getNeighbours();
        path.add(next);
        if (next.getX() == end.getX() && next.getY() == end.getY())
            break;
        else if (!visited[next.getX()][next.getY()]) {
            for (Point neighbour : neighbours) {
                if (!visited[neighbour.getX()][neighbour.getY()]) {
                    q.add(neighbour);
                }
                visited[neighbour.getX()][neighbour.getY()] = true;
            }
        }
    }
    Point current = path.removeLast();
    ArrayList<Point> v = new ArrayList<>();
    while (current.getX() != start.getX() || current.getY() != start.getY()) {
        v.add(current);
        current = path.removeLast();
    }
    return v.toArray(new Point[v.size()]);
}

编辑:

        Point current=q.peek();
    ArrayList<Point> v=new ArrayList<>();
    if(start.getX()==end.getX() && start.getY()==end.getY()) return new Point[0];
    while(current.getX()!=start.getX() || current.getY()!=start.getY()){
        v.add(current);
        current=current.parent;
    }
    return v.toArray(new Point[v.size()]);

Answer 1

第一个问题是，您将从队列中删除的所有元素添加到路径(我指的是包含path.add(next);的行)。

相反，您应该跟踪访问每个节点的父节点。当找到结束节点时，可以回溯到开始节点的步骤。

如果用尽了所有节点，但仍然没有找到结束节点，则可以返回一个空列表。

如果你需要一个MCV的例子，请告诉我，我将添加它。

后来编辑:

你需要在你的类中添加一个Point父字段，像这样:

class Point {
    int x;
    int y;
    Point parent; // reference to the Point from which this Point was visited
    // constructors, getters, setters, etc.
}

然后，您可以更改BFS实现，以便在遍历其邻居时也为当前节点设置父节点。您必须将循环更改为如下内容:

        for (Point neighbour : neighbours) {
            if (!visited[neighbour.getX()][neighbour.getY()]) {
                q.add(neighbour);
                visited[neighbour.getX()][neighbour.getY()] = true;
                neighbour.parent = next;
            }
        }