【算法】广度优先搜索算法（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); //队尾为空 }
三、例题
(adsbygoogle = window.adsbygoogle || []).push({});