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

什么是 BFS 算法(广度优先搜索)?

广度优先搜索 (BFS) 是一种用于绘制数据图或搜索树或遍历结构的算法。BFS 的全称是广度优先搜索。

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

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

什么是图遍历?

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

BFS算法的架构

ArchiBFS 算法的结构

  1. 在数据的各个层级中,你可以将任意节点标记为开始遍历的起始节点或初始节点。BFS 将访问该节点并将其标记为已访问,然后将其放入队列中。
  2. 现在 BFS 将访问最近和未访问的节点并对其进行标记。这些值也会添加到队列中。队列的工作方式如下 FIFO 模型.
  3. 以类似的方式,分析图上剩余的最近且未访问的节点,标记并添加到队列中。这些项目在收到后从队列中删除并作为结果打印。

为什么需要BFS算法?

使用 BFS 算法来搜索数据集的原因有很多。使该算法成为您的首选的一些最重要方面是:

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

BFS 算法如何工作?

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

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

因此,可以说在第一次迭代中访问并遍历了当前顶点相邻的所有节点。使用简单的队列方法来实现 BFS 算法的工作,它包括以下步骤:

步骤1)

BFS 算法的工作原理

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

步骤2)

BFS 算法的工作原理

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

步骤3)

BFS 算法的工作原理

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

步骤4)

BFS 算法的工作原理

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

步骤5)

BFS 算法的工作原理

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

步骤6)

BFS 算法的工作原理

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

步骤7)

BFS 算法的工作原理

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

示例 BFS 算法

步骤1)

示例 BFS 算法

您有一张包含 0 – 6 之间的七个数字的图表。

步骤2)

示例 BFS 算法

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

步骤3)

示例 BFS 算法

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

步骤4)

示例 BFS 算法

剩余 0 个相邻且未访问的节点被访问、标记并插入到队列中。

步骤5)

示例 BFS 算法

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

BFS算法规则

以下是使用 BFS 算法的重要规则:

  • 队列(先进先出) 数据结构 由 BFS 使用。
  • 您将图中的任何节点标记为根并开始从中遍历数据。
  • BFS 遍历图中的所有节点并不断删除它们作为完成。
  • BFS 访问相邻的未访问节点,将其标记为完成,并将其插入到队列中。
  • 如果未找到相邻顶点,则从队列中删除前一个顶点。
  • BFS 算法不断迭代,直到图中的所有顶点都被成功遍历并标记为完成。
  • 从任意节点遍历数据时均不会因BFS而产生环路。

BFS 算法的应用

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

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

总结

  • 图遍历是一个独特的过程,需要算法访问、检查和/或更新树状结构中每个未访问的节点。BFS 算法的工作原理类似。
  • 该算法可用于分析图中的节点并构建遍历这些节点的最短路径。
  • 该算法以最少的迭代次数和最短的时间遍历图。
  • BFS 选择图中的单个节点(初始点或源点),然后访问与所选节点相邻的所有节点。BFS 逐个访问这些节点。
  • BFS 将访问过并标记的数据放入队列中。队列按先进先出的方式工作。因此,首先放入图中的元素将首先被删除并作为结果打印。
  • BFS 算法永远不会陷入无限循环。
  • 由于其高精度和强大的实现,BFS 被用于 P2P 网络、网络爬虫和网络广播等多个实际解决方案中。