本文有以下内容:
广度优先搜索的描述
广度优先搜索的优点
3. 广度优先搜索的代码模版
描述:
广度优先搜索算法用于树的遍历。算法的描述概括如下:
取得当前节点
将当前节点入队列
当队列不为空时,获得队头节点head,队头head出队列;
判断队头的状态是否是待求状态
是,则作相应处理;结束算法
不是,将head的所有满足条件的子节点入队列,返回步骤II
广度优先搜索的优点:
广度优先搜索算法的适用于最短路径之类的问题,由于该算法对状态树的遍历是遵从层序遍历的,所以总是可以保证先找到的是最优的。此外,该算法的在处理某些特殊情况时,需要调整数据结构,调整的方式大致为改队列为优先队列、更改节点的数据结构(如:添加一些变量来对状态进行判断)等;具体的修改方式随需求而变。
广度优先搜索算法的代码模版
void bfs(int x,int y) { node in,out;//此处node为当前节点的数据结构 queue<node> q;//此处的queue是C++STL中的容器queue //当前节点入队列 in.x=x;in.y=y; q.push(in); //判断当前队列是否为空 while(!q.empty()) { out=q.front();//取得当前队列的队头 q.pop();//将队头出队列 if(队头满足条件) { //作相应处理 reutrn ; } else { while(当前节点out有子节点) { //获得当前节点out的满足条件的子节点 //将该子节点入队列 } } } }
本文出自 “execute” 博客,请务必保留此出处http://executer.blog.51cto.com/10404661/1764600
原文:http://executer.blog.51cto.com/10404661/1764600