第八章 广度优先搜索算法.ppt

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

2、所有未曾访问过的顶点； 4、循此以往，直到所有的顶点都被访问过为止。 这种搜索的次序体现了沿层次向横向扩展的趋势，所以称之为广度优先搜索。,【模块1】 Program bfs; 初始化，初始状态存入队列； 队列首指针head:=0; 尾指针tail:=1; while headtail do begin inc（head）；指针head后移一位，指向待扩展节点； for i:=1 to max do begin if 新节点是目标节点 then 输出并退出； if 新节点符合条件，并且新节点与原已产生的节点不重复 then tail指针加1，把新节点加入到队尾； end； end；,算法描述模

3、块（运用了队列的结构）,【模块2】 Program bfs; 初始化，初始状态存入队列； 队列首指针head:=0; 尾指针tail:=1; repeat inc（head）； 指针head后移一位，指向待扩展节点； for i:=1 to max do begin if 新节点是目标节点 then 输出并退出； if 新节点符合条件，并且新节点与原已产生的节点不重复 then tail指针加1，把新节点加入到队尾； end； until head=tail； end；,【广度优先搜索注意事项】 1、每生成一个子节点，就要提供指向它们父亲节点的指针。当解出现时候，通过逆向跟踪，可以找到从根节点

4、到目标节点的一条路径。（当然不要求输出路径的，就没必要记住父亲节点）； 2、生成的节点要与前面所有已经产生的节点比较，以免出现重复节点，浪费时间和空间，还有可能陷入死循环； 3、如果目标节点的深度与费用（如：路径长度）成正比，那么找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些，在求最优解时往往采用广度优先搜索；如果节点的费用不与深度成正比时，第一次找到的解不一定是最优解。,【算法分析】看图很容易想到用邻接矩阵来存储顶点之间的关系，0表示有通路，即有边；1表示没有通路，即没有边存在。 定义一个a数组，充当存储扩展节点的队列，ai.city记录经过的城市，ai.pre记录前驱城市，这样就

5、可以倒推出最短线路了，具体过程如下： 1、将城市A入队，队首指针为0，队尾指针为1； 2、将队首所指相连的城市依次入队（注意的是该城市在队列中未曾出现过），同时将入队城市的pre指向队首位置。然后将队首指针加1，得到新的队首城市。重复以上操作步骤，直到搜到H城市。利用pre可以倒推出最少城市线路。,例1 如图 是从 城市A到城市H 的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现在要找出一条经过城市最少的一条路线。,矩阵存储顶点关系,【参考程序】 Program ex_1; const ju:array1.8,1.8 of 0.1=( (1,0,0,0,1,0,1,1), (0,

6、1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,1,1,0), (1,1,1,1,0,0,0,1); type node=record city:char; pre:integer; end; var head,tail,i:integer; a:array1.100 of node; s:arrayA.H of boolean; procedure print(d:integer); begin write(ad.city); repe

7、at d:=ad.pre; write(-,ad.city); until ad.pre=0; end;,Procedure doit; begin fillchar(s,sizeof(s),true); head:=0; tail:=1; a1.city:=A; a1.pre:=0;sa1.city:=false; repeat inc(head); for i:=1 to 8 do if (juord(ahead.city)-64,i=0)and (schr(i+64)=true) then begin inc(tail); atail.city:=chr(i+64); atail.pre

8、:=head; satail.city:=false; if atail.city=H then begin print(tail); break; end; end; until head=tail; end; Begin doit; End.,【算法分析】 1、读入m*n矩阵阵列，将其转换成为boolean矩阵存入bz数组中； 2、沿bz数组矩阵从上到下、从左到右，找到遇到的第一个细胞； 3、将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为false； 4、将h队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为false

9、； 5、重复4，直到h队空为止，则此时找到了一个细胞； 6、重复2，直至矩阵找不到细胞； 7、输出找到的细胞个数。,例2 一矩形阵列由数字0-9组成，数字1-9代表细胞，细胞的定义是沿细胞数字上、下、左、右如果还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。,如阵列： 10 0234500067 1034560500 2045600671 0000000089,【参考程序】 program cell; const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1); var name,s:string; n,m,i,

10、j,num:integer; pic:array1.50,1.50 of integer; bz:array1.50,1.50 of boolean; h:array1.1000,1.2 of integer; procedure doit(p,q:integer); var i,t,w,x,y:integer; begin inc(num);bzp,q:=false; t:=1;w:=1;h1,1:=p;h1,2:=q; repeat for i:=1 to 4 do begin x:=ht,1+dxi;y:=ht,2+dyi; if (x0)and(x0)and(yw; end;,begi

11、n fillchar(bz,sizeof(bz),true); num:=0; readln(m,n); for i:=1 to m do begin readln(s); for j:=1 to n do begin pici,j:=ord(sj)-48; if pici,j=0 then bzi,j:=false; end; end; for i:=1 to m do for j:=1 to n do if bzi,j then doit(i,j); writeln(num); end.,上机练习,1、最短路径 如图，从入口（1）到出口（17）的可行路线图中，数字标号表示关卡。请编程求从入

12、口到出口经过最少关卡路径的算法。,提示：用邻接矩阵存储关卡之间的关系与前驱。 【输出样例】 171619181,2、迷宫问题 如图，给一个n*m的迷宫图和一个入口、一个出口。编程打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-1表示），黄色单元表示可以走（用0表示），只能往上、下、左、右四个方向走，如果无路则输出“No way！”。（注：只输出一条就可以了） 【提示】本题深搜和广搜都可以，请同学们动动脑子，有条件的可以两种方法都试试看。,program exp2; const maxn=50; dx:array1.4 of integer=(1,0,-1,0); dy:arr

13、ay1.4 of integer=(0,1,0,-1); var map:array1.maxn,1.maxn of integer; f:boolean; n,m,i,j,desx,desy,soux,souy,head,tail,x,y,k:integer; route:array1.maxn of record x,y,pre:integer;end; procedure print(d:integer); begin if routed.pre0 then begin print(routed.pre);inc(k);end; write(,routed.x,routed.y,) );

14、 end; begin readln(n,m); for i:=1 to n do for j:=1 to m do read(mapi,j); readln(soux,souy); readln(desx,desy);,f:=false;k:=1;head:=0;tail:=1;route1.x:=soux; route1.y:=souy;route1.pre:=0;mapsoux,souy:=-1; repeat inc(head); for i:=1 to 4 do begin x:=routehead.x+dxi; y:=routehead.y+dyi; if (x0)and(x0)a

15、nd(y=m)and(mapx,y=0) then begin inc(tail); routetail.x:=x;routetail.y:=y;routetail.pre:=head; mapx,y:=-1; if (x=desx)and(y=desy) then begin f:=true; print(tail); break; end; end; end; writeln; if f then begin writeln(k);break;end; until head=tail; if not f then writeln(No way!); end.,3、硬币翻转 在桌面上有一排硬币，共n枚，每一枚硬币均为正面向上。现在要把所有的硬币翻成反面向上，规则是每次可翻转任意n-1枚硬币（正面向上的被翻转为反面向上，反之亦然）。求一个最短的操作序列（将每次翻转n-1枚硬币定为一次操作