### 1. 什么是BFS **宽度优先搜索(BFS)** ：同样是一种遍历搜索树或图的算法。遍历方式为选定一个节点，接着访问所有与当前节点连接的满足条件的点。接着从这些可访问点中，按照相同的遍历方式访问每个节点，直到所有节点都被访问，这与树的层次遍历相同，时间复杂度与 DFS 相同，与搜素树和图的节点树相关。 BFS 一般用于解决最短路径，最短步骤等最优问题。 --- ### 2. BFS的搜索顺序 BFS为逐层遍历，一层一层的搜索状态  --- 利用BFS进行搜索的结果为：7 1 5 20 33 9 0 15 31 2 0 3 25 （搜索完第一层，则继续搜索第二层，第二层搜索完之后，才搜索第三层） --- ### 3. BFS采用的数据结构 实现BFS所采用的数据结构为 队列（queue） --- ### 4.DFS与BFS的区别 DFS为深度优先搜索，一条路走到底再回头 BFS为广度优先搜索，每一层遍历完之后再遍历下一层 **注意：*由于深度优先搜索会优先考虑搜索的深度。形象点说，就是不找到一个答案不回头。当答案在整棵解答树中比较稀疏时，深度优先搜索可能会先陷人过深的情况，一时半会儿找不到解。有时候需要解决连通性、最短路问题时，可以考虑使用广度优先搜索*。** --- ### 5. BFS的常规模板 #### 5.1 文字描述 BFS算法的实现是利用队列 需重复执行以下操作 1. 将根节点入队 2. 取出队头元素 3. 将队头元素能遍历到的所有状态全部入队 直至全部搜索完毕 --- #### 5.2 代码展示 ```cpp Q.push(初始状态)； // 将初始状态入队 while(!Q.empty()) { State u = Q.front(); // 取出队首 Q.pop(); // 出队 for(枚举所有可扩展状态) // 找到 u 的所有可达状态 v if(是合法的) // v 需要满足某些条件，如未访问过或未在队内等 Q.push(v); // 入队（同时可能需要维护某些必要信息） } ``` --- ### 6. 例题刨析 [洛谷 P1443 马的遍历](https://www.luogu.com.cn/problem/P1443) --- #### 6.1 文字简述 先建立一个结构体数组用于存储扩展的结点。先让起点人队，然后在队列取状态逐个扩展。容易被证明每个点被扩展到时一定是最少步数。又因为每个点只被扩展了一次，所以复杂度是 O (mn)。 --- #### 6.2 代码展示 ```cpp ```