【基本概念】
广度优先搜索（\(BFS\)）是一种图遍历算法，其核心思想是从起始节点开始，逐层地扩展搜索，直到找到目标节点或遍历完整个图。\(BFS\)按照节点的距离从起始节点开始，先访问相邻节点，然后逐层扩展到更远的节点。
\(BFS\)通常使用队列来保存待访问的节点，初始时将起始节点加入队列。然后，从队列中取出首个节点，并访问它。如果该节点是目标节点，则搜索完成。否则，将与该节点直接相邻的未访问节点加入队列，并标记它们为已访问。接下来继续从队列中取出下一个节点，直到队列为空或找到目标节点为止。
\(BFS\)的核心特点是保证找到的路径是最短路径，这是由于\(BFS\)按层次扩展搜索的方式决定的。首次找到目标节点时，即为最短路径，后续扩展的路径长度只会增加。
【基本框架】
int bfs(/*初始状态*/) {/*初始状态入队*//*标记初始状态*/while(/*队列不为空*/) {/*获取队头状态*//*队头状态出队*/if(/*判断队头状态是否目标状态*/) {/*输出结果*/return 0;}for(/*枚举决策*/) {/*以队头状态为基准获得新的状态*/if(/*状态合法性判断*/) {/*标记状态*//*记录决策*//*新状态入队*/}}}
}
【应用题目】
-
最短路径问题：广搜可以用来寻找从一个顶点到另一个顶点的最短路径，比如在无权图中寻找两点之间的最短路径。
-
连通性问题：广搜可以用来判断两个顶点之间是否存在路径，即判断图中的连通性。
-
图的遍历：广搜可以用来遍历整个图的节点，例如查找一个图中所有与某个顶点相邻的节点。
-
迷宫问题：广搜可以用来解决迷宫问题，即在一个迷宫中找到从起点到终点的路径。