//广度优先搜索//

同样是一种遍历搜索树或图的算法。遍历方式为选定一个节点，接着访问所有与当前节点连接的满足条件的点。接着从这些可访问点中，按照相同的遍历方式访问每个节点，直到所有节点都被访问，这与树的层次遍历相同，时间复杂度与 DFS 相同，与搜索树和图的节点树相关。 BFS 一般用于解决最短路径，最短步骤等最优问题。

//BFS的搜索顺序//

BFS为逐层遍历，一层一层的搜索状态 即,搜索完第一层，则继续搜索第二层，第二层搜索完之后，才搜索第三层

//BFS采用的数据结构//

实现BFS所采用的数据结构为 队列（queue）

//DFS与BFS的区别//

DFS为深度优先搜索，一条路走到底再回头 BFS为广度优先搜索，每一层遍历完之后再遍历下一层

注意：由于深度优先搜索会优先考虑搜索的深度。形象点说，就是不找到一个答案不回头。当答案在整棵解答树中比较稀疏时，深度优先搜索可能会先陷人过深的情况，一时半会儿找不到解。有时候需要解决连通性、最短路问题时，可以考虑使用广度优先搜索。

//BFS的常规模板//

Q.push(初始状态)； // 将初始状态入队 
while(!Q.empty()) 
{
 State u = Q.front(); // 取出队首
 Q.pop(); // 出队 
 for(枚举所有可扩展状态) // 找到 u 的所有可达状态 v
   if(是合法的) // v 需要满足某些条件，如未访问过或未在队内等
     Q.push(v); // 入队（同时可能需要维护某些必要信息） 
}

//BFS算法原理//

BFS算法的实现是利用队列 需重复执行以下操作 将根节点入队 取出队头元素 将队头元素能遍历到的所有状态全部入队 直至全部搜索完毕

bye~