广度优先搜索 (BFS) 算法示例

什么是 BFS 算法（广度优先搜索）？

广度优先搜索（BFS）是一种用于处理图数据、搜索树或遍历结构的算法。BFS 的全称是广度优先搜索。

该算法能够以精确的广度方式高效地访问并标记图中的所有关键节点。该算法选择图中的单个节点（初始点或源点），然后访问与所选节点相邻的所有节点。请记住，BFS 会逐个访问这些节点。

一旦算法访问并标记了起始节点，它就会向最近的未访问节点移动并进行分析。访问后，所有节点都会被标记。这些迭代持续进行，直到图中的所有节点都已成功访问和标记。

什么是图遍历？

图遍历是一种常用的定位图中顶点位置的方法。它是一种高级搜索算法，可以快速准确地分析图，并标记访问顶点的顺序。此过程使您能够快速访问图中的每个节点，而不会陷入无限循环。

BFS算法的架构

1. 在数据的各个层级中，您可以将任何节点标记为起始节点或初始节点，以便开始遍历。广度优先搜索（BFS）将访问该节点，将其标记为已访问，并将其放入队列中。
2. 现在，BFS 将访问最近且尚未访问过的节点并标记它们。这些值也会被添加到队列中。队列的工作原理是…… FIFO 模型.
3. 类似地，对图中剩余的最近且未访问的节点进行分析、标记，并将其添加到队列中。这些节点在接收到后立即从队列中删除，并将结果打印出来。

为什么需要BFS算法？

使用广度优先搜索（BFS）算法搜索数据集有很多原因。以下几个关键因素使其成为首选算法：

• BFS 可用于分析图中的节点并构建遍历这些节点的最短路径。
• BFS 可以用最少的迭代次数遍历整个图。
• BFS 算法的架构简单且健壮。
• 与其他算法相比，BFS 算法的结果具有较高的准确性。
• BFS 迭代是无缝的，并且该算法不可能陷入无限循环问题。

BFS 算法如何工作？

图遍历要求算法访问、检查和/或更新树状结构中每个未访问的节点。图遍历按访问图上节点的顺序进行分类。

BFS 算法从图中的第一个或起始节点开始操作并彻底遍历它。一旦成功遍历初始节点，就会访问并标记图中的下一个未遍历的顶点。

因此，可以说在第一次迭代中，所有与当前顶点相邻的节点都被访问和遍历了。广度优先搜索（BFS）算法的实现采用了一种简单的队列方法，其步骤如下：

步骤1）

图中的每个顶点或节点都是已知的。例如，您可以将节点标记为 V。

步骤2）

如果顶点 V 未被访问，则将顶点 V 添加到 BFS 队列中。

步骤3）

开始 BFS 搜索，完成后，将顶点 V 标记为已访问。

步骤4）

BFS 队列仍然不为空，因此从队列中删除图的顶点 V。

步骤5）

检索图中所有与顶点 V 相邻的剩余顶点。

步骤6）

对于每个相邻顶点，假设为 V1，如果它尚未被访问，则将 V1 添加到 BFS 队列中。

步骤7）

BFS 将访问 V1，将其标记为已访问，并将其从队列中删除。

示例 BFS 算法

步骤1）

你有一张图表，上面有七个数字，范围从 0 到 6。

步骤2）

0 或零已被标记为根节点。

步骤3）

0 被访问、标记并插入到队列数据结构中。

步骤4）

其余的 0 邻接且未访问过的节点将被访问、标记并插入队列。

步骤5）

重复遍历迭代，直到访问所有节点。

BFS算法规则

以下是使用广度优先搜索算法的重要规则：

• 队列（FIFO – 先进先出） 数据结构 由 BFS 使用。
• 你可以将图中任意节点标记为根节点，然后从该节点开始遍历数据。
• 广度优先搜索（BFS）遍历图中的所有节点，并保留丢弃的节点。ping 它们已完成。
• BFS 访问相邻的未访问节点，将其标记为完成，并将其插入到队列中。
• 如果没有找到相邻顶点，则从队列中移除前一个顶点。
• BFS 算法会不断迭代，直到成功遍历图中的所有顶点并标记为已完成。
• 从任意节点遍历数据时均不会因BFS而产生环路。

BFS 算法的应用

让我们看一下 BFS 算法实现非常有效的一些实际应用。

• 非加权图： BFS 算法能够以最高的准确度，在最短的时间内轻松创建最短路径和最小生成树，从而访问图中的所有顶点。
• P2P 网络： 广度优先搜索（BFS）可用于在对等网络中定位所有最近或相邻的节点。这将更快地找到所需数据。
• 网络爬虫： 搜索引擎或网络爬虫可以通过使用 BFS 轻松构建多级索引。BFS 实现从源（即网页）开始，然后访问来自该源的所有链接。
• 导航系统： BFS 可以帮助从主要位置或源位置找到所有邻近位置。
• 网络广播： 广播数据包由 BFS 算法引导，查找并到达其具有地址的所有节点。

常见问题