4.3 BFS

4.3.1 数据结构-队列

4.3.2 BFS算法的实现

1. 初始化：
• 创建一个队列Q，用于存储待访问的节点。
• 创建一个数组visited，用于标记已访问过的节点。
• 将起始节点放入队列，并标记为已访问。

2. 循环遍历：
• 当队列不为空时，执行以下操作：
• 从队列中弹出（或称为“出队”）一个节点，记为v ，若节点v 就是目标节点goal ，则提前返回。
• 访问节点v的所有未访问的邻接节点。
• 对于每个未访问的邻接节点，将其加入队列，并标记为已访问，同时记录当前节点v为邻接节点的父节点。

3. 回溯路径：
• 从目标节点开始，通过父节点向回追溯，直到起始节点，最终得到一条路径。

4.3.3 BFS算法的图解

1. 初始化一个空的队列和一个空的数组，其中队列用来存储未被访问过的节点，数组用来存储节点是否被访问过。

2. 将节点0 放入队列，并将其标记为已访问。

3. 从队列头部移除节点0 ，并将其未被访问过的邻接节点（1，2）放入队列，邻接节点（1，2）的父节点是0 。

4. 从队列头部移除节点1 ，并将其未被访问过的邻接节点（3）放入队列，邻接节点（3）的父节点是1 。

5. 从队列头部移除节点2 ，并将其未被访问过的邻接节点（4）放入队列，邻接节点（4）的父节点是2 。

6. 从队列头部移除节点3 ，并将其未被访问过的邻接节点（无）放入队列。

7. 从队列头部移除节点4 ，节点4 即为目标节点，BFS算法遍历结束，并通过回溯父节点找到一条路径（0 —> 2—> 4）。

4.3.4 BFS算法特点

• 优点：
• 可以找到从起点到终点的最短路径（在无权图中）。
• 实现简单，易于理解和实现。

• 缺点：
• 需要较多的存储空间来保存待访问的节点（使用队列）。
• 在有权图中，BFS不一定能找到最短路径（因为BFS只考虑路径上的边数，而不考虑边的权重）。

4.3.5 参考