查找从源到其他节点的最短路径

广度优先搜索 (BFS)是用于遍历或搜索树或图数据结构的算法。它从树根(或图的某个任意节点,有时称为搜索键)开始,并在移动到下一级邻居之前首先探索邻居节点。BFS 是由爱德华·福雷斯特·摩尔Edward Forrest Moore)于 20 世纪 50 年代末发明的,他用它来寻找迷宫中的最短路径,并在 1961 年被 CY Lee 独立发现为线路路由算法。

BFS 算法的过程在这些假设下工作:

  1. 我们不会多次遍历任何节点。
  2. 源节点或我们开始的节点位于 0 级。
  3. 我们可以直接从源节点到达的节点是 1 级节点,我们可以从 1 级节点直接到达的节点是 2 级节点,依此类推。
  4. 水平表示距离源的最短路径的距离。

我们来看一个例子: StackOverflow 文档

让我们假设这个图表示多个城市之间的连接,其中每个节点表示一个城市,两个节点之间的边缘表示有一条连接它们的道路。我们想要从节点 1节点 10 。所以节点 1 是我们的,它是 0 级。我们将节点 1 标记为已访问。我们可以从这里转到节点 2节点 3节点 4 。所以他们将是等级(0 + 1) = 等级 1 节点。现在我们将它们标记为已访问并与它们一起工作。

StackOverflow 文档

访问彩色节点。我们当前使用的节点将标记为粉红色。我们不会两次访问同一个节点。从节点 2节点 3节点 4 ,我们可以转到节点 6,节点 7节点 8 。让我们将它们标记为已访问。这些节点的级别为 level(1 + 1) = level 2StackOverflow 文档

如果你没有注意到,节点级别只是表示距离的最短路径距离。例如:我们在第 2 级找到了节点 8 。因此,从节点 8 的距离是 2 。 **** **** **** ****

我们还没有到达我们的目标节点,即节点 10 。那么让我们访问下一个节点。我们可以直接从节点 6节点 7节点 8 转到。 StackOverflow 文档

我们可以看到,我们发现节点 10 处于第 3 级。因此,从节点 10 的最短路径是 3. 我们逐级搜索图形并找到最短路径。现在让我们擦除我们没有使用的边缘: StackOverflow 文档

删除我们没有使用的边缘后,我们得到一棵名为 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 转到节点 7level [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 是边数。