Breadth First Search

广度优先搜索（Breadth-First Search, BFS） 是一种用于遍历或搜索树或图的算法。不同于DFS，它从一个起始节点开始，首先访问所有相邻的节点，然后再逐层向外扩展，访问下一个层级的节点，直到所有节点都被访问或找到目标节点为止。

BFS 基本步骤:

1. 初始化：创建一个队列来存储待访问的节点，并将起始节点加入队列。同时，创建一个集合或数组来记录已访问的节点，以避免重复访问。
2. 访问节点：
   • 从队列中取出一个节点，标记为已访问。
   • 访问该节点并处理（例如，打印节点值或检查是否为目标节点）。
   • 将所有未被访问的相邻节点加入队列。
3. 重复：重复步骤 2，直到队列为空或找到目标节点。

BFS 的特点

• 层次遍历：BFS 按层次访问节点，适合用于寻找最短路径（在无权图中）。
• 使用队列：BFS 使用队列来管理待访问的节点，确保先访问的节点先被处理。
• 时间复杂度：对于图的 BFS，时间复杂度为 $O(V+E)$ ，其中 $V$ 是节点数，$E$ 是边数。
• 空间复杂度：空间复杂度通常为 $O(V)$，用于存储队列和已访问节点。

BFS 的应用

• 最短路径：在无权图中，BFS 可以用于寻找从起始节点到目标节点的最短路径。
• 图的连通性：可以用来检查图的连通性。
• 层次遍历：在树结构中，BFS 可以用于层次遍历，输出每一层的节点。
• 网络流：在网络流问题中，BFS 用于寻找增广路径。