【算法】广度优先搜索算法(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); //队尾为空 }
三、例题
扫描二维码推送至手机访问。
版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。