图的广度优先搜索或 BFS

什么是图？

图是一种数据结构，我们将值以节点或顶点的形式存储。节点之间通过边连接，边可以是加权的也可以是未加权的。

如果两个节点之间存在边且该边包含一些权重，则我们称之为加权图。否则，称为未加权图。

未加权图是一种没有边权重的图。在这种类型的图中，边表示两个节点之间的连接。如果未加权图中节点 u 和 v 之间存在边，则 u 和 v 相互相邻。

为了遍历图，我们使用两种方法

• 一种是 DFS（深度优先搜索）
• 另一种是 BFS（广度优先搜索）

在 DFS 中，我们使用递归访问起始节点的所有最深节点。这里，我们讨论的是 BFS。

BFS

BFS 代表**广度优先搜索**，我们遍历源节点的所有相邻节点，然后依次解决相邻节点的问题。在 BFS 中，节点的遍历是径向进行的。

例如

下一次迭代-

下一次迭代-

下一次迭代-

在上面的例子中，BFS 的顺序将是：0->1,2->3,4->5,6

我们将使用队列数据结构来获取图的 BFS 遍历。

Java 代码

输出

说明

在上面的例子中，我们有一个连接图，形式为邻接列表，其中每个节点都有其邻居节点的 ArrayList。

现在要实现 BFS 遍历，我们使用一个初始为空的队列数据结构，并且还使用一个布尔类型的访问数组，以确保我们不会包含已经在广度优先搜索遍历中覆盖的节点。

最初，我们将源节点标记为已访问并将其添加到队列中。现在，我们将迭代循环直到队列变空。每次，我们将移除队列中最上面的元素，将其添加到我们的答案中，并将其未访问的邻居添加到队列中并将其标记为已访问。

第一次迭代-

队列中有节点 0，我们将它添加到我们的答案中，它的邻居节点 1 和 2 将被添加到队列中并标记为已访问。

现在 q=1,2 且 answer=0。

现在我们将移除 1 并将其添加到我们的答案中，其未访问的邻居是 3。

所以现在 q=2,3 且 answer =0,1

现在我们将移除 2，将其添加到我们的答案中，其未访问的邻居是 4。

所以现在 q=3,4 且 answer = 0,1,2

现在我们将移除 3，将其添加到我们的答案中，其未访问的邻居为空。

所以现在 q=4 且 answer = 0,1,2,3

现在我们将移除 4，将其添加到我们的答案中，其未访问的邻居是 5,6。

所以现在 q=5,6 且 answer = 0,1,2,3,4

现在我们将移除 5，将其添加到我们的答案中，其未访问的邻居为空。

所以现在 q=6 且 answer = 0,1,2,3,4,5

现在我们将移除 6，将其添加到我们的答案中，其未访问的邻居为空。

所以现在 q=空 且 answer = 0,1,2,3,4,5,6

由于队列为空，我们将停止循环并从函数返回，然后打印结果。

时间复杂度：O(N+E)，其中 N 是节点数，E 是边数

空间复杂度：O(N) -> 访问数组 O(N) 用于结果 + O(N) 用于队列。

如果图不连通

如果图不连通，那么图将有多个源顶点。

因此，我们将为每个分量单独调用 BFS。

例如

Java 代码

输出

时间复杂度：O(N+E)，其中 N 是节点数，E 是边数