BFS 不返回路径

Question

我正在尝试在给定起点和终点的二维数组上实现 BFS。我试着在网格上给函数两个点，但它 returns 是一个空数组，意味着没有路径。

谁能指出我哪里出错了，如果可能的话帮我改正错误？谢谢

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); 的行）。

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

如果你已经用完了所有的节点，你仍然没有找到结束节点，你可以return一个空列表。

如果您需要 MCV example，请告诉我，我会添加。

稍后编辑：

您需要向 class 添加一个 Point parent 字段，如下所示：

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;
            }
        }

BFS 不返回路径

BFS not returning a path

java

algorithm

path-finding

breadth-first-search