Java- 广度优先搜索迷宫最短路径

Question

我似乎有一个问题，不太明白如何检索广度优先搜索算法发现的最短路径。目前，如果可以到达迷宫的出口，该算法就能正常工作。在另一篇帖子中，有人提到在将节点标记为已访问后，保持父节点的跟踪。

我尝试了一个简单的实现，通过在Point结构中包含一个父Point来跟踪父节点，但是当我在Grid上标记路径时，它标记了迄今为止所遍历的所有路径，我相信我可能已经搞砸了如何跟踪父节点。

有没有人知道我哪里错了。 也许我错过了一些简单的东西？ 以下是代码供参考。

迷宫是一个二维整数网格。 假设1是墙壁，0是可移动路径。

Point类包含： Point Parent int x, y; 除此之外什么都没有。

public Point BFS(int x, int y){
    Queue<Point> Path = new Queue<>();

    Path.enqueue(new Point(x,y));//push current on queue

    Point Cur = Path.front();//make current point
    //test code for recursive backcall of path
        Cur.setParent(null);
    //test code for recursive backcall of path


    Point end = new Point(mWidth-2, mHeight-2);//set goal

    while((!Path.isEmpty())){
        Point old = Cur;

        Cur = Path.dequeue();
        Cur.setParent(old);

        if(Cur.compareto(end)){
            return Cur;//return Point then traverse up from here calling Cur.Parent to get path.
        }
        else if(Maze[Cur.getX()][Cur.getY()]==1){//Enque all possible paths

            Maze[Cur.getX()][Cur.getY()] = 2;//mark as visitied
            if(Cur.getX()-1>=0)
                if(Maze[Cur.getX()-1][Cur.getY()]==1)
                    Path.enqueue(new Point(Cur.getX()-1,Cur.getY()));

            if(Cur.getX()+1<mWidth)
                if(Maze[Cur.getX()+1][Cur.getY()]==1)
                    Path.enqueue(new Point(Cur.getX()+1,Cur.getY()));

            if(Cur.getY()-1>=0)
                if(Maze[Cur.getX()][Cur.getY()-1]==1)
                    Path.enqueue(new Point(Cur.getX(),Cur.getY()-1));

            if(Cur.getY()+1<mHeight)
                if(Maze[Cur.getX()][Cur.getY()+1]==1)
                    Path.enqueue(new Point(Cur.getX(),Cur.getY()+1));
        }

    }
    return null;
}

- Michael Wright

Answer 1

看起来在多次迭代后，old不再是父节点。你可以在将点添加到队列时设置其父节点，例如：

Point next = new Point(Cur.getX()-1,Cur.getY());
next.setParent(Cur);
Path.enqueue(next);

当你找到结尾时，调用getParent()直到它为null，就能够获取回到开头的路径。

- fgb

---

谢谢。我知道我哪里错了。非常感谢。它起作用了。 - Michael Wright