首页 第8章广度优先搜索

第8章广度优先搜索

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

第八章广度优先搜索广度优先搜索的过程广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。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 题。例如　图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展第２６个结点，总共生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。【例1】图4表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。【算法分析】看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。如图。首先想到的是用队列的思想。a数组是存储扩展结点的队列，a[i]记录经过的城市,b[i]记录前趋城市，这样就可以倒推出最短线路。具体过程如下：（1）将城市A入队，队首为0、队尾为1。（2）将队首所指的城市所有可直通的城市入队（如果这个城市在队列中出现过就不入队，可用一布尔数组s[i]来判断），将入队城市的前趋城市保存在b[i]中。然后将队首加1，得到新的队首城市。重复以上步骤，直到搜到城市H时，搜索结束。利用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[101];bools[9];//初始化intout(intd)//输出过程{cout<usingnamespacestd;intdx[4]={-1,0,1,0},dy[4]={0,1,0,-1};intbz[100][100],num=0,n,m;voiddoit(intp,intq){intx,y,t,w,i;inth[1000][2];num++;bz[p][q]=0;t=0;w=1;h[1][1]=p;h[1][2]=q;//遇到的第一个细胞入队do{t++;//队头指针加1for(i=0;i<=3;i++)//沿细胞的上下左右四个方向搜索细胞{x=h[t][1]+dx[i];y=h[t][2]+dy[i];if((x>=0)&&(x=0)&&(y 设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。【算法分析】该题是一个路径搜索问题，根据图示，从入口（1）到出口（17）可能有多条途径，其中最短的路径只有一条，那么如何找最短路径呢？根据题意，用数组NO存储各关卡号，用数组PRE存储访问到某关卡号的前趋关卡号。其实本题是一个典型的图的遍历问题，我们可以采用图的广度优先遍历，并利用队列的方式存储顶点之间的联系。从入口（1）开始先把它入队，然后把（1）的所有关联顶点都入队，即访问一个顶点，将其后继顶点入队，并存储它的前趋顶点，……，直到访问到出口（17）。最后，再从出口的关卡号（17）开始回访它的前趋关卡号，……，直到入口的关卡号（1），则回访的搜索路径便是最短路径。从列表中可以看出出口关卡号（17）的被访问路径最短的是：（17）←（16）←（19）←（18）←（1）由此，我们得到广度优先遍历求最短路径的基本方法如下：假设用邻接矩阵存放路线图（a[I][j]=1表示I与j连通，a[I][j]=0表示I与j不连通）。再设一个队列和一个表示拓展到哪个顶点的指针变量pos。（1）从入口开始，先把（1）入队，并且根据邻接矩阵，把（1）的后继顶点全部入队，并存储这些后继顶点的前趋顶点为（1）；再把pos后移一个，继续拓展它，将其后继顶点入队，并存储它们的前趋顶点，……，直到拓展到出口（目的地（17））；注意后继顶点入队前，必须要检查这个顶点是否已在队列中，如果已经在了就不要入队了；这一步可称为图的遍历或拓展；（2）从队列的最后一个关卡号（出口（17））开始，依次回访它的前驱顶点，倒推所得到的路径即为最短路径。主要是依据每个顶点的前趋顶点倒推得到的。实现如下：i=1；WHILE(NO[I]!=17)++i;DO{cout<<"("<usingnamespacestd;intn,m,desx,desy,soux,souy,totstep,a[51],b[51],map[51][51];boolf;intmove(intx,inty,intstep){map[x][y]=step;//走一步，作标记，把步数记下来a[step]=x;b[step]=y;//记路径if((x==desx)&&(y==desy)){f=1;totstep=step;}else{if((y!=m)&&(map[x][y+1]==0))move(x,y+1,step+1);//向右if((!f)&&(x!=n)&&(map[x+1][y]==0))move(x+1,y,step+1);//往下if((!f)&&(y!=1)&&(map[x][y-1]==0))move(x,y-1,step+1);//往左if((!f)&&(x!=1)&&(map[x-1][y]==0))move(x-1,y,step+1);//往上}}intmain(){inti,j;cin>>n>>m;//n行m列的迷宫for(i=1;i<=n;i++)//读入迷宫，0表示通，-1表示不通for(j=1;j<=m;j++)cin>>map[i][j];cout<<"inputtheenter:";cin>>soux>>souy;//入口cout<<"inputtheexit:";cin>>desx>>desy;//出口f=0;//f=0表示无解；f=1表示找到了一个解move(soux,souy,1);if(f){for(i=1;i<=totstep;i++)//输出直迷宫的路径cout<usingnamespacestd;intu[5]={0,0,1,0,-1},w[5]={0,1,0,-1,0};intn,m,i,j,desx,desy,soux,souy,head,tail,x,y,a[51],b[51],pre[51],map[51][51];boolf;intprint(intd){if(pre[d]!=0)print(pre[d]);//递归输出路径cout<>n>>m;//n行m列的迷宫for(i=1;i<=n;i++)//读入迷宫，0表示通，-1表示不通for(j=1;j<=m;j++)cin>>map[i][j];cout<<"inputtheenter:";cin>>soux>>souy;//入口cout<<"inputtheexit:";cin>>desx>>desy;//出口head=0;tail=1;f=0;map[soux][souy]=-1;a[tail]=soux;b[tail]=souy;pre[tail]=0;while(head!=tail)//队列不为空{head++;for(i=1;i<=4;i++)//4个方向{x=a[head]+u[i];y=b[head]+w[i];if((x>0)&&(x<=n)&&(y>0)&&(y<=m)&&(map[x][y]==0)){//本方向上可以走tail++;a[tail]=x;b[tail]=y;pre[tail]=head;map[x][y]=-1;if((x==desx)&&(y==desy))//扩展出的结点为目标结点{f=1;print(tail);break;}}}if(f)break;}if(!f)cout<<"noway."<

                    本文档为【第8章广度优先搜索】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

第8章广度优先搜索

你可能还喜欢