什么是广度优先搜索算法

广度优先搜索算法（BreadthFirst Search，简称 BFS）是一种用于遍历或搜索树或图的算法，它从根节点（或任意选定的节点）开始，探索尽可能靠近起点的所有节点，然后逐层向外扩展，直到找到目标节点或遍历完所有可达节点。

（图片来源网络，侵删）

基本原理：

1、起始点：选择一个节点作为起始点，将其标记为已访问。

2、队列：使用一个队列来存储待访问的节点，初始时将起始点加入队列。

3、访问相邻节点：从队列中取出一个节点，访问它的所有未被访问过的邻居节点。

4、标记和入队：将访问过的邻居节点标记为已访问，并将它们加入队列。

5、重复过程：重复步骤3和步骤4，直到队列为空或找到目标节点。

特点：

1、保证最先找到的是最短路径（在不带权图中）。

2、可以找到从一个节点到另一个节点的所有路径（如果需要）。

3、适用于在非加权图中搜索最短路径问题。

应用场景：

1、社交网络中找到两个人之间的最短联系路径。

2、在棋盘类游戏中寻找所有可能的走法。

3、网络爬虫中用于遍历网页。

算法流程：

1、初始化：设置起始节点为当前节点。

2、检查当前节点：判断当前节点是否为目标节点。

如果是，结束搜索并回溯路径。

3、添加到队列：将当前节点加入队列。

4、扩展节点：从队列中取出节点，访问其所有未访问的邻居。

对每个邻居，检查是否为目标节点。

如果不是，将其加入队列，并记录路径信息。

5、循环执行：重复步骤24，直到队列为空或找到目标节点。

示例：

广度优先搜索算法通常用在图的层次结构不深，且需要尽快找到最短路径的情况下，它是一种简单直观的搜索策略，易于实现，并且在无权图中能够保证找到最短路径。