广度优先搜索

一种基础的图遍历算法，通过分层探索节点，系统地调查从起点出发的所有可到达顶点。

定义

广度优先搜索（BFS）是一种系统性的遍历或搜索图和树结构的策略，从给定的源节点开始，按层级顺序访问节点，确保在处理更深层节点之前先处理所有相邻节点。它使用队列来管理探索前沿，该队列保持已发现节点的处理顺序。BFS在无权图中特别有效，可用于查找到目标节点的最短路径（以边数计）以及进行广度优先分析。这种方法在有限图中保证完备性，意味着如果存在有效解，它将找到该解。BFS还奠定了许多图算法和网络、人工智能及数据分析等实际应用的基础。

优点

• 由于按层级顺序进行，总能找到无权图中的最短路径。
• 保证完备性：在有限搜索空间中，若存在解，它将找到该解。
• 遍历顺序可预测且系统，适用于许多分析任务。
• 使用标准队列数据结构实现简单。
• 支持构建最短路径树和多种算法应用。

缺点

• 内存消耗可能较大，因为它需要存储每层的所有前沿节点。
• 与深度优先方法相比，对非常深或大的图效率较低。
• 在高度互联的数据集上性能可能下降，因为前沿范围较广。
• 需要额外的记录来避免在循环图中重复访问节点。
• 未经修改不适用于带权图（例如需使用迪杰斯特拉算法）。

应用场景

• 从种子URL开始的网络爬虫和结构化链接探索。
• 在无权网络（如社交图）中查找最短路径或连接。
• 树的层序遍历，如二叉树的广度扩展。
• 人工智能、机器人路径规划和迷宫求解中的最短路径发现。
• 连通性检查和生成树等高级图算法的基础。