第八章 广度优先搜索算法

第八章广度优先搜索算法广度优先搜索算法是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。如Dijkstra单源最短路径和Prim最小生成树算法都采用了广度优先搜索的思想。核心思想：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点，若没有，再用算符逐一扩展第二层的所有节点…，如此依次扩展，检查下去，直到发现目标节点为止。即：1、从图中的某一顶点v0开始，先访问v0；2、访问所有与v0相邻接的顶点v1、v2…；3、依次访问与v1、v2…vt相邻接的所有未曾访问过的顶点；4、循此以往，直到所有的顶点都被访问过为止。这种搜索的次序体现了沿层次向横向扩展的趋势，所以称之为广度优先搜索。【模块1】Programbfs;初始化，初始状态存入队列；队列首指针head:=0;尾指针tail:=1;whileheadtaildobegininc（head）；指针head后移一位，指向待扩展节点；fori:=1tomaxdobeginif新节点是目标节点then输出并退出；if新节点符合条件，并且新节点与原已产生的节点不重复thentail指针加1，把新节点加入到队尾；end；end；算法描述模块（运用了队列的结构）【模块2】Programbfs;初始化，初始状态存入队列；队列首指针head:=0;尾指针tail:=1;repeatinc（head）；指针head后移一位，指向待扩展节点；fori:=1tomaxdobeginif新节点是目标节点then输出并退出；if新节点符合条件，并且新节点与原已产生的节点不重复thentail指针加1，把新节点加入到队尾；end；untilhead=tail；end；【广度优先搜索注意事项】1、每生成一个子节点，就要提供指向它们父亲节点的指针。当解出现时候，通过逆向跟踪，可以找到从根节点到目标节点的一条路径。（当然不要求输出路径的，就没必要记住父亲节点）；2、生成的节点要与前面所有已经产生的节点比较，以免出现重复节点，浪费时间和空间，还有可能陷入死循环；3、如果目标节点的深度与费用（如：路径长度）成正比，那么找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些，在求最优解时往往采用广度优先搜索；如果节点的费用不与深度成正比时，第一次找到的解不一定是最优解。【算法分析】看图很容易想到用邻接矩阵来存储顶点之间的关系，0表示有通路，即有边；1表示没有通路，即没有边存在。定义一个a数组，充当存储扩展节点的队列，a[i].city记录经过的城市，a[i].pre记录前驱城市，这样就可以倒推出最短线路了，具体过程如下：1、将城市A入队，队首指针为0，队尾指针为1；2、将队首所指相连的城市依次入队（注意的是该城市在队列中未曾出现过），同时将入队城市的pre指向队首位置。然后将队首指针加1，得到新的队首城市。重复以上操作步骤，直到搜到H城市。利用pre可以倒推出最少城市线路。例1如图是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现在要找出一条经过城市最少的一条路线。ABDCGHFE10001111H01100111G01111100F00111011E10111010D11100110C11011110B11010001AHGFEDCBA矩阵存储顶点关系【参考程序】Programex_1;constju:array[1..8,1..8]of0..1=((1,0,0,0,1,0,1,1),(0,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));typenode=recordcity:char;pre:integer;end;varhead,tail,i:integer;a:array[1..100]ofnode;s:array[‘A’..’H’]ofboolean;procedureprint(d:integer);beginwrite(a[d].city);repeatd:=a[d].pre;write(‘--------’,a[d].city);untila[d].pre=0;end;Proceduredoit;beginfillchar(s,sizeof(s),true);head:=0;tail:=1;a[1].city:=‘A’;a[1].pre:=0;s[a[1].city]:=false;repeatinc(head);fori:=1to8doif(ju[ord(a[head].city)-64,i]=0)and(s[chr(i+64)]=true)thenbegininc(tail);a[tail].city:=chr(i+64);a[tail].pre:=head;s[a[tail].city]:=false;ifa[tail].city=‘H’thenbeginprint(tail);break;end;end;untilhead=tail;end;Begindoit;End.【算法分析】1、读入m*n矩阵阵列，将其转换成为boolean矩阵存入bz数组中；2、沿bz数组矩阵从上到下、从左到右，找到遇到的第一个细胞；3、将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为false；4、将h队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为false；5、重复4，直到h队空为止，则此时找到了一个细胞；6、重复2，直至矩阵找不到细胞；7、输出找到的细胞个数。例2一矩形阵列由数字0-9组成，数字1-9代表细胞，细胞的定义是沿细胞数字上、下、左、右如果还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。如阵列：4100234500067103456050020456006710000000089【参考程序】programcell;constdx:array[1..4]of-1..1=(-1,0,1,0);dy:array[1..4]of-1..1=(0,1,0,-1);varname,s:string;n,m,i,j,num:integer;pic:array[1..50,1..50]ofinteger;bz:array[1..50,1..50]ofboolean;h:array[1..1000,1..2]ofinteger;proceduredoit(p,q:integer);vari,t,w,x,y:integer;begininc(num);bz[p,q]:=false;t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;repeatfori:=1to4dobeginx:=h[t,1]+dx[i];y:=h[t,2]+dy[i];if(x0)and(x=m)and(y0)and(y=n)and(bz[x,y])thenbegininc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;end;inc(t);untiltw;end;beginfillchar(bz,sizeof(bz),true);num:=0;readln(m,n);fori:=1tomdobeginreadln(s);forj:=1tondobeginpic[i,j]:=ord(s[j])-48;ifpic[i,j]=0thenbz[i,j]:=false;end;end;fori:=1tomdoforj:=1tondoifbz[i,j]thendoit(i,j);writeln(num);end.上机练习1、最短路径如图，从入口（1）到出口（17）的可行路线图中，数字标号表示关卡。请编程求从入口到出口经过最少关卡路径的算法。11872341258610911141315161719提示：用邻接矩阵存储关卡之间的关系与前驱。【输出样例】1716191812、迷宫问题如图，给一个n*m的迷宫图和一个入口、一个出口。编程打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-1表示），黄色单元表示可以走（用0表示），只能往上、下、左、右四个方向走，如果无路则输出“Noway！”。（注：只输出一条就可以了）【提示】本题深搜和广搜都可以，请同学们动动脑子，有条件的可以两种方法都试试看。-1-10000000出口00000-1-100-1-1-100000-1-1000-10000-1000000-10入口programexp2;constmaxn=50;dx:array[1..4]ofinteger=(1,0,-1,0);dy:array[1..4]ofinteger=(0,1,0,-1);varmap:array[1..maxn,1..maxn]ofinteger;f:boolean;n,m,i,j,desx,desy,soux,souy,head,tail,x,y,k:integer;route:array[1..maxn]ofrecordx,y,pre:integer;end;procedureprint(d:integer);beginifroute[d].pre0thenbeginprint(route[d].pre);inc(k);end;write('(',route[d].x,',',route[d].y,')');end;beginreadln(n,m);fori:=1tondoforj:=1tomdoread(map[i,j]);readln(soux,souy);readln(desx,desy);f:=false;k:=1;head:=0;tail:=1;route[1].x:=soux;route[1].y:=souy;route[1].pre:=0;map[soux,souy]:=-1;repeatinc(head);fori:=1to4dobeginx:=route[head].x+dx[i];y:=route[head].y+dy[i];if(x0)and(x=n)and(y0)and(y=m)and(map[x,y]=0)thenbegininc(tail);route[tail].x:=x;route[tail].y:=y;route[tail].pre:=head;map[x,y]:=-1;if(x=desx)and(y=desy)thenbeginf:=true;print(tail);break;end;end;end;writeln;iffthenbeginwriteln(k);break;end;untilhead=tail;ifnotfthenwriteln('Noway!');end.3、硬币翻转在桌面上有一排硬币，共n枚，每一枚硬币均为正面向上。现在要把所有的硬币翻成反面向上，规则是每次可翻转任意n-1枚硬币（正面向上的被翻转为反面向上，反之亦然）。求一个最短的操作序列（将每次翻转n-1枚硬币定为一次操作）。【输入样例】4【输出样例】4｛操作次数｝0111｛每次操作后硬币状态，0表示正面向上，1表示反面向上｝110000011111readln(n);writeln(n);fori:=1tondoa[i]:=0;fori:=1tondobeginforj:=1tondoifjithenifa[j]=0thena[j]:=1elsea[j]:=0;fork:=1tondowrite(a[k]);writeln;end;