图的广度优先搜索的应用◆内容提要广度优先搜索是分层次搜索，广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。

本讲座就最短路径问题、分酒问题、八数码问题三个典型的范例，从问题分析、算法、数据结构等多方面进行了讨论，从而形成图的广度优先搜索解决问题的模式，通过本讲座的学习，能明白什么样的问题可以采用或转化为图的广度优先搜索来解决。

在讨论过程中，还同时对同一问题进行了深层次的探讨，进一步寻求解决问题的最优方案。

◆知识讲解和实例分析和深度优先搜索一样，图的广度优先搜索也有广泛的用途。

由于广度优先搜索是分层次搜索的，即先将所有与上一层顶点相邻接的顶点搜索完之后，再继续往下搜索与该层的所有邻接而又没有访问过的顶点。

故此，当某一层的结点出现目标结点时，这时所进行的步骤是最少的。

所以，图的广度优先搜索广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。

本次讲座就几个典型的范例来说明图的广度优先搜索的应用。

先给出图的广度优先搜索法的算法描述：F:=0;r:=1;L[r]:=初始值;H:=1;w:=1;bb:=true;While bb dobeginH:=h+1;g[h]:=r+1;For I:=1 to w doBeginF:=f+1;For t:=1 to 操作数doBegin⑴m:=L[f]; {出队列}；⑵判断t操作对m结点的相邻结点进行操作;能则设标记bj:=0,并生成新结点;不能,则设标记bj:=1;if bj:=0 then {表示有新结点生成}beginfor k:=1 to g[h]-1 doif L[k]=新结点then {判断新扩展的结点是否以前出现过}beginbj:=1;k:=g[h]-1end;if bj<>1 then {没有出现过} beginr:=r+1;L[r]:=新结点;{新结点进队列}b[r]:=f;c[r]:=t;{并链接指针，保存操作数} end; end; end; end;w:=r+1-g[h];s:=0;{计算新生成的一层的结点数}for k:=g[h] to r do {在新生成的一层结点中，判断是否有目标结点存在} if L[k]=目标结点 then begins:=s+1; {累计解的条数} 根据链接指针求出路径； end;if s:<>0 then begin输出s 条路径；bb:=false; {设程序结束条件} end; end;例1：最短路径问题求从任意一个顶点V i 出发，对给出的图，求到达任意顶点V j （i<>j ）的所有最短路径 [问题分析]1、首先用邻接表表示此图各端点的邻接关系。

2、数据结构4 78constd:array[1..8,1..4] of byte=((2,3,4,0),(1,3,7,0),(1,2,4,5),(1,3,6,0),(3,6,7,8),(4,5,8,0),(2,5,8,0),(5,6,7,0)){二维数组存放邻接表}n:array[1..8] of byte=(3,3,4,3,4,3,3,3); {存放邻接顶点数}varL：array[1..64] of byte {队列}F,r:byte {f队头指针，r队尾指针}B:array[1..64] of byte {链接表，表示某一个结点的前趋结点}G:array[1..10] of byte {表示层结点的首结点在队列开始的位置}H:byte {搜索的层次}由于搜索过的点不再进行搜索，故设置一个数组E[M]为标记，表示结点M是否访问过e:array[1..8] of 0..1;{用1表示已访问过，0表示还没有访问}c:array[1..8,1..8]of byte; {C[s,j]存储到达目标结点后各最短路径的线路}bb:Boolean {搜索结束标记}3、算法描述⑴设立初值，并令起始结点进队：f:=0;r:=1;lL[r]:=st,E[st]:=1;w:=1;h:=1;⑵将此时第h层（开始h=1，表示第一层）的w（开始时w=1，表示一个结点）顶点的顺序出队，并访问与该层各顶点相邻接但又没有访问过的顶点，同时将这些结点进队列，且设立前趋链接指针和访问过标记，若此时的结点为目标结点，则只设立前趋链接指针而不设立访问过标记⑶计算此时第h+1层的顶点个数w:=r+1-g[h]，然后看该层有多少个顶点为目标结点，凡是出现目标顶点的，就将其个数累计，也就是为最短路径的条数，同时从这个目标结点按前趋链接指针将到达该目标结点的路径的各个顶点编号存入c[s,j]中，然后转⑷，若目标顶点累计个数为0，表明该层没有出现目标结点，则转⑵。

⑷打印搜索到的各条最短路径的各结点编号，并结束程序。

程序如下：(见exp7_1.pas)program exp7_1;constd:array[1..8,1..4] of byte=((2,3,4,0),(1,3,7,0),(1,2,4,5),(1,3,6,0),(3,6,7,8),(4,5,8,0),(2,5,8,0),(5,6,7,0));n:array[1..8] of byte=(3,3,4,3,4,3,3,3);varL,b:array[1..64] of byte;F,r,h,m,st,ed,I,j,t,k,s,p,w:byte;G:array[1..10] of byte;e:array[1..8] of 0..1;c:array[1..8,1..8]of byte;bb:Boolean;beginwrite('start:');readln(st);write('end:');readln(ed);fillchar(e,sizeof(e),0); {标记数组清零}fillchar(c,sizeof(c),0); {路径数组清零}f:=0;r:=1;L[r]:=st;h:=1;w:=1;bb:=true;while bb dobeginh:=h+1;g[h]:=r+1; {记录h+1层的首地址}for i:=1 to w dobeginf:=f+1;m:=L[f];e[m]:=1; {取队首结点，并设访问过标记}for t:=1 to n[m] do {依次访问m结点的相邻结点}if e[d[m,t]]=0 then {若m的相邻结点没有访问过}beginr:=r+1;L[r]:=d[m,t];b[r]:=f; {则进队列}end;end;w:=r+1-g[h]; {计算第h层的新结点数目}s:=0;for k:=g[h] to r do {检查第h层上的新结点是否存在目标结点}if L[k]=ed then {等于目标结点}begins:=s+1;p:=b[k];j:=1;c[s,j]:=L[k];while p<>1 dobegin j:=j+1;c[s,j]:=L[p];p:=b[p]; end;j:=j+1;c[s,j]:=L[p];for t:=j downto 1 doif t=1 then writeln(c[s,t]) else write(c[s,t],'－→');end;if s<>0 thenbeginwriteln(st,'－→',ed,'total=',s,'step=',j-1);bb:=false;end;end;end.输入：start:1end:8输出：1－→2－→7－→81－→3－→5－→81－→4－→6－→81－→8 total=3 step=3输入：start:2end:6输出：2－→1－→4－→6 2－→3－→4－→6 2－→3－→5－→6 2－→7－→5－→6 2－→7－→8－→6 2－→1－→4－→62－→6 total=5 step=3 推广应用（作业题1）：如下图表示的是从城市A 到城市H 的交通图，从图中可以看出，从城市A 到城市H 要经过若干个城市。

现要找出一条经过城市最少的一条路线。

例2：分酒问题有一8斤酒瓶装满酒，没有量器，只有两个分别能装5斤和3斤的空酒瓶。

试设计一程序将8斤酒对分为两个4斤，并以最少的步骤给出答案。

[问题分析]1、 分析在倒酒过程中，看起来是每一次倒酒，上面的六种操作都可能进行，然而有此操作却是无意义的。

如8斤瓶空时，则8→3、8→5是无意义的。

又如8斤瓶满时，则5→8、3→8操作无意义。

因此，每次倒酒操作后，都必须知道此时三个酒瓶到底多少酒，这样才能准确判断此时何种操作不能进行，何种操作可以进行。

为了表示每操作一次后各酒瓶中的酒量，设变量M 表示8斤瓶在进行第i 操作后装的酒量，N 表示5斤瓶在进行第i 操作后装的酒量，A 表示3斤瓶在进行第i 操作后装的酒量，由于整个酒量为8，所有A=8-M-N 。

对以上六种操作能和不能进行的条件如下：8→5操作：不能进行的条件为：N=5或M=0能进行时，剩余量为：N=N+M ，此时如果N>5，则M=N-5，N=5，否则M=0 8→3操作：不能进行的条件为：8-N-M=3或M=0 能进行时，剩余量为：如果M<3-（8-M-N ），则M=0，否则M=5-N ，N 不变 5→8操作：不能进行的条件为：M=8或N=0能进行时，剩余量为：M=N+M 且N=0 5→3操作：不能进行的条件为：8-N-M=3或N=0能进行时，剩余量为：如果N<3-（8-M-N ），则N=0，否则N=5-M ，M 不变 3→8操作：不能进行的条件为：8-N-M=0或M=8 能进行时，剩余量为：M=8-N ，N 不变A B C D G E FH3→5操作：不能进行的条件为：8-N-M=0或N=5能进行时，剩余量为：N=8-M，M不变2、定义数据结构constd:array[1..6] of string[4]=(‘8->5’,’8->3’,’5->8’,’5-3’,’3-8’,’3-5’); {6种操作}varL:array[1..50,1..2] of shortint; {表示倒酒后8斤和5斤瓶中的剩余量}B:array[1..50] of shortint; {每一层的各结点的前趋结点的链指针}C: array[1..50] of shortint; {每进行一次操作的操作数}E:array[1..10,1..20] of shortint;{最少步骤的所有解中，该层各结点是由上一层各结点通过何种操作而得到的操作数}X,y:array[1..10,1..20] of shortint ;{在最少步骤所有解中，各层的结点其8斤和5斤瓶中的剩余量}G:array[1..20] of shortint; {各层结点的首结点在队列的位置}F,r,h,w,n,m:shortint; {f为队列首指针，r为队列尾指针，m,n分别表示8斤和5斤瓶中的剩余量，h为搜索的层数，w为每一层结点的个数}3、算法描述：⑴设立队首队尾指针初值，f=0,r=1。