C#BFS最后一次访问节点

Question

我正在努力让BFS在网格系统上找到最佳路径。

目前，它一直工作到找到结束节点。但没有发出任何路径，因为我不知道如何做到这一点。BFS如何记录路径的最佳节点？

BFS算法功能(按下按钮执行(：

public void BFS()
{
rq.Enqueue(start.X);
cq.Enqueue(start.Y);
gridmatrix[start.X, start.Y].VISITED = true;
while (rq.Count() > 0)
{
int r = rq.Dequeue();
int c = cq.Dequeue();
if (r == end.X && c == end.Y)
{
endfound = true;
break;
}
explore_neighbours(r,c);

nodesleftinlayer--;
if(nodesleftinlayer == 0)
{
nodesleftinlayer = nodesinnextlayer;
nodesinnextlayer = 0;
BFSMoveCount++;
}
if(endfound == true)
{
Console.WriteLine(BFSMoveCount);

}
else
{
Console.WriteLine(-1);
}


}
}

查找当前节点的所有相邻节点的功能：

void explore_neighbours(int r, int c)
{

for (int i = 0; i < 4; i++) {
int rr = r + dr[i]; //direction array
int cc = c + dc[i];

if(rr < 0 || cc < 0)
{
continue;
}
if(rr >= gridmatrix.GetLength(0) || cc >= gridmatrix.GetLength(1))
{
continue;
}
if(gridmatrix[rr,cc].VISITED == true)
{
continue;
}
if(gridmatrix[rr,cc].COLOUR == 1)
{
continue;
}
rq.Enqueue(rr);
cq.Enqueue(cc);
gridmatrix[rr, cc].VISITED = true;
if(gridmatrix[rr, cc] == gridmatrix[end.X, end.Y])
{
endfound = true;
}
if(gridmatrix[rr,cc].COLOUR != 4 && gridmatrix[rr,cc].COLOUR != 1) //If grid tile has been checked
{
gridmatrix[rr, cc].COLOUR = 6; //set colour on the grid to pink
}


nodesinnextlayer++;
}
}

Answer 1

有两种常见的方法可以导出路径：

1. 您可以记住每个访问的单元格从起点到终点的距离，然后当您找到终点时，您会沿着每走一步都会减少距离的路径走回起点。当您可以对访问的顶点使用位压缩表示时，这种方法具有内存效率，因为您只需要记住距离的最低2位。

2. 你可以直接记住每个访问单元格的前一个单元格，当你找到结束时，你只需按照所有这些链接回到开始。

您可能应该使用方法(1(。这两种方法中的任何一种都适合你。不是为找到的每个点存储VISITED=true，而是存储距起点的距离或前一个网格点的坐标。