查找从源到其他节点的最短路径
广度优先搜索 (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 是边数。