第8章广度优先搜索.ppt

《第8章广度优先搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章广度优先搜索广度优先搜索的过程广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即⒈从图中的某一顶点V0开始，先访问V0

2、；⒉访问所有与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(新结点与原已产生结点重复)删

3、去该结点（取消入队，tail减1）;elseif(新结点是目标结点)输出并退出；}}}while(head

4、点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。下面我们看看怎样用宽度优先搜索来解决八数码问题。例如　图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展第２６个结点，总共生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。【例1】图4表示的是从城市A到城市H的交通图。从图中可

5、以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。【算法分析】看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。如图。首先想到的是用队列的思想。a数组是存储扩展结点的队列，a[i]记录经过的城市,b[i]记录前趋城市，这样就可以倒推出最短线路。具体过程如下：（1）将城市A入队，队首为0、队尾为1。（2）将队首所指的城市所有可直通的城市入队（如果这个城市在队列中出现过就不入队，可用一布尔数组s[i]来判断），将入队城市的前趋城市保存在b[i]中。然后将队首加1，得到新的队首城市。重复以上步骤，直到搜到城市H时，搜索结束。利

6、用b[i]可倒推出最少城市线路。【参考程序】#include#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[10

7、1];bools[9];//初始化intout(intd)//输出过程{cout<

8、==0)&&(s[i]==0))//判