特点：
1.利用队列进行数据存储
2.在边权为1的图中第一次遍历到的点一定是与起点的距离最小的点
3.遍历方式为逐层遍历
4.所需存储空间大

模板：

 void bfs()
{
    queue<int> q;//一般用stl库中的queue来实现队列比较方便
    q.push(起点S);//将初始状态入队
    标记初始状态已入队。
    while(!q.empty())//队列不为空就执行入队出队操作
    {
        top = q.front();//取出队首
        q.pop();//队首出队
        for (枚举所有可扩展的状态)
        {
            if (check())//状态合法
            {
                q.push(temp);//状态入队
                标记成已入队。
            }

        }
    }

题型：
1.FloodFill：
利用bfs特性搜索到每一块具有相同特性的连通块

基础 池塘计数
求连通块的个数

变式1 城堡问题
新点入队条件增加限制，增加求最大连通块的点数

变式2 山峰与山谷
连通块具有特性，且需要特性判断。采用八向遍历
2.最短路模型：
利用bfs特性（在边权为1的图中第一次遍历到的点一定是与起点的距离最小的点）完成起点到终点的最小距离判断
搜索过程接近于dijkstra算法，因为队列始终保持两个特性（两端性：队列中始终只存在距离x的点与距离x+1的点）（单调性：队列中，点的距离单调由小到大递增，可能相同但不会减小）所以能用dijkstra来证明算法正确性，能用dijkstra就能用bfs求最短路。

基础 迷宫问题
典，四向遍历出新的能入队的点，第一个遍历到终点的点的距离即为最短距离

变式1 武士风度的牛
遍历方式改为象棋中马的日字形遍历

变式2 抓住那头牛
二维改为一维

3.多源bfs：
矩阵距离
求一个点到多个终点的最小距离，那就把所有终点初始化距离为0入队，第一个遍历到所求点的就是最小距离

4.最小步数模型：
将最短路中的点变成复杂状态，将通过变化后的另一个复杂状态入队，求出起点状态到最终状态的最小步数
基础 八数码
状态为字符串类型，用string队列储存，距离使用unordered_map储存，状态变化先用一维坐标变为二维坐标，然后进行二维位置变化后再化为一维新可行状态入队

变式1 魔板
遍历方式变化，需要输出操作序列（利用prev哈希表记录由上一个状态到本状态的操作X和上一个状态）在最后逆向遍历到起点后用reverse（）输出正向操作序列

？仍未搞清楚如何按字典序大小输出？

5.双端队列广搜：
电路维修
图抽象为数学模型的难度增加，将边权为0的点插入到队头，将边权为1的点插入到队尾(为了维持两端性和单调性从而保证算法的正确性)，使用deque双端队列实现

优化方式：
1.双向广搜：
！在已知起点状态和终点状态且一个状态可拓展到另一个状态的个数很多导致单向遍历会出现tle或mle情况下使用！
假设每次决策数量是 K，限制步数为10那么如果直接BFS，最坏情况下的搜索空间是K的10次方，非常大，所以会TLE或者MLE。如果采用双向BFS，则可以把搜索空间降到 2*k的5次方。在实际测试中只需 20ms 左右，剪枝效果很好。
BFS的扩展方式是：分别枚举在原字符串中使用替换规则的起点，和所使用的的替换规则、
具体思路：
起点和终点各创建一个队列和距离表，判断队列长度，队列小的进行拓展一层（若拓展规则逆向不相同则需要逆向处理规则），若在拓展过程中遍历到一个点在对面的距离表上有合法记录，则该点为两边最短路径的交接点
例题：字串变换

2.A*算法：
A*算法：当前点距离起点的真实距离+当前点距离终点的预估距离<=起点到终点的真实距离；
预估距离由估价函数f计算得出，具体函数随具体题目而变，本题预估距离为该点的数字位置距离终点数字位置的曼哈顿距离。