第八章广度优先搜索算法

1、第八章第八章 广度优先搜索算法广度优先搜索算法 广度优先搜索算法是最简便的图的搜索算法之一，这一广度优先搜索算法是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。如算法也是很多重要的图的算法的原型。如Dijkstra单源最短路单源最短路径和径和Prim最小生成树算法都采用了广度优先搜索的思想。最小生成树算法都采用了广度优先搜索的思想。 核心思想：从初始节点开始，应用算符生成第一层节点，核心思想：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二

2、层节点，并逐一检则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点，若没有，再用算符逐一扩查第二层节点中是否包含目标节点，若没有，再用算符逐一扩展第二层的所有节点展第二层的所有节点，如此依次扩展，检查下去，直到发现，如此依次扩展，检查下去，直到发现目标节点为止。即：目标节点为止。即： 1、从图中的某一顶点、从图中的某一顶点v0开始，先访问开始，先访问v0； 2、访问所有与、访问所有与v0相邻接的顶点相邻接的顶点v1、v2； 3、依次访问与、依次访问与v1、v2vt相邻接的所有未曾访问过的顶相邻接的所有未曾访问过的顶点；点； 4、循此以往，直到所有的顶点都被访问

3、过为止。、循此以往，直到所有的顶点都被访问过为止。 这种搜索的次序体现了沿层次向横向扩展的趋势，所以称这种搜索的次序体现了沿层次向横向扩展的趋势，所以称之为广度优先搜索。之为广度优先搜索。 【模块【模块1】Program bfs; 初始化，初始状态存入队列；初始化，初始状态存入队列； 队列首指针队列首指针head:=0; 尾指针尾指针tail:=1; while head0)and(x0)and(yw; end;begin fillchar(bz,sizeof(bz),true); num:=0; readln(m,n); for i:=1 to m do begin readln(s); f

4、or 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）的可行路线图中，数字标号表示）的可行路线图中，数字标号表示关卡。请编程求从入口到出口经过最少关卡路径的算法。关卡。请编程求从入口到出口经过最少关卡路径的算法。1187234125861

5、0911141315161719提示：用邻接矩阵存储关卡提示：用邻接矩阵存储关卡之间的关系与前驱。之间的关系与前驱。【输出样例【输出样例】 1716191812、迷宫问题、迷宫问题 如图，给一个如图，给一个n*m的迷宫图和一个入口、一个出口。编程打印一条的迷宫图和一个入口、一个出口。编程打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-1表表示），黄色单元表示可以走（用示），黄色单元表示可以走（用0表示），只能往上、下、左、右四个表示），只能往上、下、左、右四个方向走，如果无路则输出方向走，如果无路则输出“No way！”

6、。（注：只输出一条就可以了）。（注：只输出一条就可以了）【提示】本题深搜和广搜都可以，请同学们动动脑子，有条件的可以【提示】本题深搜和广搜都可以，请同学们动动脑子，有条件的可以两种方法都试试看。两种方法都试试看。-1-1000000000000-1-100-1-1-100000-1-1000-10000-1000000-10program exp2; const maxn=50; dx:array1.4 of integer=(1,0,-1,0); dy:array1.4 of integer=(0,1,0,-1); var map:array1.maxn,1.maxn of integer;

7、 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,) ); end; begin readln(n,m); for i:=1 to n do for j:=1 to m do read(map

8、i,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)and(y=m)and(mapx,y=0) then begin inc(tail); routetail.x:=x;routetail.

9、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枚硬币定为一次操作）。枚硬币定为一次操作）。 【输入样例【输入样例】 4 【输出样例【输出样例】 4 操作次数操作次数 0111 每次操作后硬币状态，每次操作后硬币状态，0表示正面向上，表示正面向上，1表示反面向上表示反面向上 1100 0001 1111 readln(n);writ