第八章广度优先搜索广度优先搜索的过程广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即⒈从图中的某一顶点V0开始，先访问V0；⒉访问所有与V0相邻接的顶点V1，V2，......，Vt；⒊依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；⒋循此以往，直至所有的顶点都被访问过为止。这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。广度优先搜索算法描述：intBfs(){初始化，初始状态存入队列；队列首指针head=0;尾指针tail=1；do{指针head后移一位，指向待扩展结点；for(inti=1;i<=max;++i)//max为产生子结点的规则数{if(子结点符合条件){tail指针增1，把新结点存入列尾；if(新结点与原已产生结点重复)删去该结点（取消入队，tail减1）;elseif(新结点是目标结点)输出并退出；}}}while(head#includeusingnamespacestd;intju[9][9]={{0,0,0,0,0,0,0,0,0},{0,1,0,0,0,1,0,1,1},{0,0,1,1,1,1,0,1,1},{0,0,1,1,0,0,1,1,1},{0,0,1,0,1,1,1,0,1},{0,1,1,0,1,1,1,0,0},{0,0,0,1,1,1,1,1,0},{0,1,1,1,0,0,1,1,0},{0,1,1,1,1,0,0,0,1}};inta[101],b[101];bools[9];//初始化intout(intd)//输出过程{cout<
