简单的bfs示例......我不明白

Question

我试图了解BFS如何使用队列来确定最短路径.假设我有一个网格:

1--2--3
|  |  |
4--5--6
|  |  |
7--8--9
|
0

起始点为'9',目标为'0'.

所以......我推动了......

push 9 {9}
pop 9 {}
push 6 {6}
push 8 {6,8}
pop 6 {8}
push 3 {8,3}
push 5 {8,3,5}
pop 8 {3,5}
push 7 {3,5,7}
pop 3 {5,7}
push 2 {5,7,2}
pop 5 {7,2}
push 4 {7,2,4}
pop 7 {2,5}
found 0

如何从这个混乱中提取最短的路径？我不知道这是如何给我提供最短路径的.我想错了吗？

谢谢!

Answer 1

为了找到最短的路径,每个节点还应该"记住"你在BFS期间如何到达它[哪个顶点导致发现它].

在cpp中,您可以使用a map<int,int>来实现它.
简单的例子:

map[9] = -1; //indicationg source
map[6] = 9;
map[8] = 9;
map[3] = 6;
map[7] = 8 ;
...
map[0] = 7;

要获得最短路径,只需遵循从0到源[当值为-1时]的路径.