【算法】广度优先搜索算法（BFS）
一、广度优先搜索的过程
广度优先搜索算法（又称宽度优先搜索算法，BFS）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
广度优先算法的核心思想是：从初节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点，若没有，再用算符逐一扩展第二层所有节点。如此依次扩展，检查下去，直到发现目标节点为止。即：
从图中的某一顶点v0开始，先访问v0;
访问所有与v0相邻的顶点v1,v2,v3，...，vt
依次访问与v1,v2,...,vt相邻的所有未曾访问过的顶点
循环以往，直至所有的顶点都被访问过为止。
实现方式有 数组模拟队列，和 队列方式实现。
一般走迷宫类型既可以用bfs也可以用dfs，求最短路径类问题用bfs较多。
二、广度优先搜索算法描述
数组版：
int bfs(){
初始化，初始状态存入队列；
队列首指针 head=0; 尾指针 tail=1;
do{
指针head 后移一位，指向待扩展结点；
for(int i=1; i<=max;i++){ //max 为产生子结点的规则数
if(子结点符合条件){
tail指针增1，把新结点存入队尾；
if(新结点与原已产生结点重复)删除该结点（取消入队，tail减1）；
else{
if(新结点是目标结点) 输出并退出；
}
}
}
} while(head<tail); //队尾为空
}队列版：
queue<数据类型> q;
while(!q.empty){
int head=q.front();
q.pop();
for(枚举）
if(合法)
q.push();
}
四、其他例题
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
