查找从源到其他节点的最短路径
广度优先搜索 （BFS）是用于遍历或搜索树或图数据结构的算法。它从树根（或图的某个任意节点，有时称为搜索键）开始，并在移动到下一级邻居之前首先探索邻居节点。BFS 是由爱德华·福雷斯特·摩尔 （ Edward Forrest Moore）于 20 世纪 50 年代末发明的，他用它来寻找迷宫中的最短路径，并在 1961 年被 CY Lee 独立发现为线路路由算法。
BFS 算法的过程在这些假设下工作：
- 我们不会多次遍历任何节点。
- 源节点或我们开始的节点位于 0 级。
- 我们可以直接从源节点到达的节点是 1 级节点，我们可以从 1 级节点直接到达的节点是 2 级节点，依此类推。
- 水平表示距离源的最短路径的距离。
我们来看一个例子： 
让我们假设这个图表示多个城市之间的连接，其中每个节点表示一个城市，两个节点之间的边缘表示有一条连接它们的道路。我们想要从节点 1 到节点 10 。所以节点 1 是我们的源，它是 0 级。我们将节点 1 标记为已访问。我们可以从这里转到节点 2 ，节点 3 和节点 4 。所以他们将是等级（0 + 1） = 等级 1 节点。现在我们将它们标记为已访问并与它们一起工作。
访问彩色节点。我们当前使用的节点将标记为粉红色。我们不会两次访问同一个节点。从节点 2 ，节点 3 和节点 4 ，我们可以转到节点 6，节点 7 和节点 8 。让我们将它们标记为已访问。这些节点的级别为 level（1 + 1） = level 2 。 
如果你没有注意到，节点级别只是表示距离源的最短路径距离。例如：我们在第 2 级找到了节点 8 。因此，从源到节点 8 的距离是 2 。 **** **** **** ****
我们还没有到达我们的目标节点，即节点 10 。那么让我们访问下一个节点。我们可以直接从节点 6 ，节点 7 和节点 8 转到。 
我们可以看到，我们发现节点 10 处于第 3 级。因此，从源到节点 10 的最短路径是 3. 我们逐级搜索图形并找到最短路径。现在让我们擦除我们没有使用的边缘： 
删除我们没有使用的边缘后，我们得到一棵名为 BFS 树的树。此树显示从源到所有其他节点的最短路径。
所以我们的任务是从源到 1 级节点。然后从 1 级到 2 级节点，依此类推，直到我们到达目的地。我们可以使用队列来存储我们要处理的节点。也就是说，对于我们要使用的每个节点，我们将推送所有其他可以直接遍历并且尚未遍历队列的节点。
模拟我们的例子：
首先，我们将源推送到队列中。我们的队列将如下所示：
front
+-----+
| 1 |
+-----+
节点 1 的级别为 0. level [1] = 0 。现在我们开始我们的 BFS。首先，我们从队列中弹出一个节点。我们得到节点 1 。我们可以从这一个转到节点 4 ，节点 3 和节点 2 。我们从节点 1 到达了这些节点。所以 level [4] = level [3] = level [2] = level [1] + 1 = 1 。现在我们将它们标记为已访问并将它们推入队列中。
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
现在我们弹出节点 4 并使用它。我们可以从节点 4 转到节点 7 。 level [7] = level [4] + 1 = 2 。我们将节点 7 标记为已访问并将其推入队列中。 **** **** **** **** **** ****
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
从节点 3 ，我们可以转到节点 7 和节点 8 。由于我们已经将节点 7 标记为已访问，因此我们将节点 8 标记为已访问，我们更改级别[8] = 级别[3] + 1 = 2 。我们将节点 8 推入队列中。
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
此过程将持续到我们到达目的地或队列变空。的水平阵列为我们提供了从最短路径的距离源。我们可以使用无穷大值初始化级别数组，这将标记尚未访问的节点。我们的伪代码将是： **
Procedure BFS(Graph, source):
Q = queue();
level[] = infinity
level[source] := 0
Q.push(source)
while Q is not empty
u -> Q.pop()
for all edges from u to v in Adjacency list
if level[v] == infinity
level[v] := level[u] + 1
Q.push(v)
end if
end for
end while
Return level
通过迭代级别数组，我们可以找出每个节点与源的距离。例如： 节点 10 与源的距离将存储在级别[10]中。
有时我们可能不仅需要打印最短距离，而且还需要打印从源头到达目标节点的路径。为此，我们需要保留父数组。 parent [source] 将为 NULL。对于级别数组中的每个更新，我们只需在 for 循环中的伪代码中添加 parent[v] := u。在完成 BFS 之后，为了找到路径，我们将遍历父数组，直到我们到达源，这将由 NULL 值表示。伪代码将是：
Procedure PrintPath(u): //recursive | Procedure PrintPath(u): //iterative
if parent[u] is not equal to null | S = Stack()
PrintPath(parent[u]) | while parent[u] is not equal to null
end if | S.push(u)
print -> u | u := parent[u]
| end while
| while S is not empty
| print -> S.pop
| end while
复杂：
我们曾经访问过每个节点一次，每个边缘一次。因此复杂度将为 O（V + E） ，其中 V 是节点数， E 是边数。