广度优先搜索（Breadth First Search）

广度优先搜索简称BFS，是一种以“广度”为第一关键词的算法，当碰到岔道口时，总是优先考虑从该岔道口能直接到达的所有节点，以此类推，直到所有节点都被访问位置，类似于掉入水面的石子，激起的水波纹总是以石子掉落点为圆心向周围以圆的方式扩散开来。 BFS的运行方式类似于队列，所以，基本上所有的BFS题目大多都采用队列的形式来解决，例：对于当前模拟到的任意一个元素，将其按规定条件能访问到的每一个元素按访问次序入队，接着遵循以上的规律逐个处理队列内的元素，直到队列空为止，对队列的操作遵循模板如下：

#include<queue>
using namespace std;
void bfs(int temp){
          
   //这里的int型temp可以是任意类型，下面队列中存入的数据也可以是任意类型
    queue<int> q;
    q.push(temp);
    //这里可以存在不同的定义与操作
    while(!q.empty()){
          
   
        //取出队首元素top
        //访问队首元素top
        //将队首元素出队
        //将top的下一层结点中未曾入队的结点全部入队，并设置为已入队
    }
}

1. 定义需要输入的变量与常量并初始化inq与题目的样例输入数组以及增量数组等（不是必须）
2. 定义bool 类型的判断函数judge为了未来在bfs函数的whule循环中使用
3. 定义最重要的bfs函数，bfs函数内部遵循本笔记上方的模板代码
4. 定义main函数 总之，BFS永远是以广度为优先考虑项注重于搜索时按层搜索”地毯式“，而一般问题的答案，就是BFS搜索到某一最终目的地所使用的最短层数其次，在BFS中设置的inq数组含义是”当前枚举到的元素是否已入过队“而不是”当前元素是否已被访问“，因为如果标记为true的条件是是否已被访问，那么就会出现某个节点已经因为地毯式的搜索而已经在队列中存在，但是对于正常的遍历顺序来讲它还未被访问，就可能会出现在接下来的顺序遍历中再次将该元素二次入队，这样会导致计算量大大增加。 最后注意一点：C++STL中的queue函数对于入队的push操作只是对其生成了一个该入队元素的副本，而不是传入了该元素的指针或者引用，所以对队列中的元素访问改变不会对初始的原本元素有任何改变，自然，改变原始元素也不会改变队列中的元素。