Data Structures Algorithms 简明教程
Breadth First Search (BFS) Algorithm
Breadth First Search (BFS) Algorithm
广度优先搜索 (BFS) 算法以广度优先的方式遍历图，以搜索符合一组条件的节点的图数据结构。当在任何迭代中出现死角时，它使用队列记住下一个开始搜索的顶点。
广度优先搜索 (BFS) 算法从树根开始，在移动到下一层级的节点之前探索当前层级中的所有节点。
正如以上给出的示例，BFS 算法首先从 A 到 B 到 E 到 F，然后到 C 和 G，最后到 D。它采用以下规则。
-
Rule 1 − 访问相邻的未访问过的顶点。将其标识为已访问。显示它。将其插入队列。
-
Rule 2 − 如果未找到相邻顶点，则从队列中删除第一个顶点。
-
Rule 3 − 重复规则 1 和规则 2，直至队列为空。
在此阶段，我们只剩下未标记（未访问）的节点。但根据算法，我们会不断出列以获取所有未访问的节点。当队列清空后，程序结束。