广度优先遍历与最短路径学习笔记

广度优先遍历

广度优先遍历（BFS）是一种用于图形或树数据结构的算法。该算法从起点开始，逐层遍历到所有可达节点，直到找到目标节点。广度优先遍历通常使用队列来实现，每个节点在进入队列之前都被标记为已访问。

算法实现

1. 将起点加入队列
2. 对于队列中的每个节点，找到它的所有邻居节点并将其加入队列
3. 标记当前节点为已访问
4. 从队列中取出下一个节点并重复步骤2-3，直到队列为空或找到目标节点

实例

在以下 5x5 的网格中，我们希望从起点 (0, 0) 到达终点 (4, 4)。每个方格表示一个节点，其中蓝色方格表示障碍，无法通过。

Copy Code
0 0 0 0 0
0 1 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0

我们可以使用 BFS 算法来寻找到达终点的最短路径。首先，我们将起点 (0, 0) 加入队列，并标记它为已访问。然后，我们处理队列中的下一个节点 (0, 1)，并发现它有两个邻居节点 (1, 1) 和 (0, 2)，将它们加入队列。接着，我们处理队列中的 (1, 1)，并发现它有两个邻居节点 (1, 2) 和 (2, 1)，将它们加入队列。不断重复这个过程，直到找到终点 (4, 4)。

最短路径

最短路径是指在图形或树数据结构中寻找从起点到目标节点的路径，该路径具有最小的边权或路径长度。

算法实现

在基于 BFS 算法的基础上，我们可以使用队列来存储从起点到当前节点的路径。每当我们发现新的邻居节点时，我们将其加入队列，并在队列中一起存储它们到起点的路径。

实例

以下是一个无向带权图的示例，其中节点 A-D 分别表示不同城市，边表示两个城市之间的距离。我们需要找到从城市 A 到城市 D 的最短路径。

我们可以使用 Dijkstra 算法或 A* 算法来寻找最短路径。在此我们以 Dijkstra 算法为例。首先，我们将起点 A 加入队列，并将其到起点的距离设为 0。然后，我们处理队列中的下一个节点，发现从 A 可以达到的三个邻居节点 B、C、D，我们将它们加入队列并记下它们到 A 的距离。接着，我们从队列中取出当前距离 A 最近的节点 B 并重复这个过程，直到找到终点 D。最后，我们可以通过记录每个节点的前驱节点来构建从起点到终点的最短路径。