资源描述：
《【精品】浅谈DFS》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、广度优先搜索是分层次搜索，广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。像最短路径问题、分酒问题、八数码问题都是典型的DFS.例1：最短路径问题求从任意一个顶点Vi出发，对给出的图，求到达任意顶点Vj(iOj)的所有最短路径[问题分析]1、首先用邻接表表示此图各端点的邻接关系。顶点123456782、21113425接邻顶点3323655647467887个数33434333数据结构constd:array[1..&1..4]ofbyte=((2,3,4,0),(1,3,7,0),(1,2,4,5),(1,3,6,0),(3,6,7,8),(
2、4,5,8,0),(2,5,&0),(5,6,7,0))｛二维数组存放邻接表｝n:array[1..8]ofbyte=(3,3,4,3,4,3,3,3);｛存放邻接顶点数｝L：array[1..64]ofbyte｛队列｝F,r:byte｛f队头指针,r队尾指针｝B:array[l..64]ofbyte｛链接表，表示某一个结点的前趋结点｝G:array[l..10]ofbyte｛表示层结点的首结点在队列开始的位置｝H:byte｛搜索的层次｝山于搜索过的点不再进行搜索，故设置一个数组E[M]为标记，表示结点M是否访问过e:array[1..8]of0..1
3、;｛用1表示已访问过，0表示述没有访问｝c:array[1..8,1.•8]ofbyte;｛C[s,j]存储到达目标结点后各最短路径的线路｝bb:Boolean｛搜索结束标记｝3、算法描述⑴设立初值，并令起始结点进队：f:=0;r:=l;lL[r]:二st,E[st]:=1;w:=l;h:=l;⑵将此时第h层(开始h二1,表示第一层)的¥(开始时W二1,表示一个结点)顶点的顺序出队，并访问与该层各顶点相邻接但乂没有访问过的顶点，同时将这些结点进队列，且设立前趋链接指针和访问过标记，若此时的结点为日标结点，则只设立前趋链接指针而不设立访问过标记⑶计算此
4、时第h+1层的顶点个数w:=r+l-g[h],然后看该层有多少个顶点为目标结点，凡是出现日标顶点的，就将其个数累计，也就是为最短路径的条数，同时从这个1=1标结点按前趋链接指针将到达该目标结点的路径的各个顶点编号存入c[s,j]中，然片转⑷，若目标顶点累计个数为0,表明该层没有出现日标结点，则转⑵。⑷打印搜索到的各条最短路径的各结点编号，并结束程序。程序如下:(见exp7_l.pas)programexp71;constd:array[1..8,1・・4]ofbyte=((2,3,4,0),(1,3,7,0),(1,2,4,5),(1,3,6,0),(
5、3,6,7,8),(4,5,8,0),(2,5,&0),(5,6,7,0));n:array[1..8]ofbyte=(3,3,4,3,4,3,3,3);varL,b:array[1..64]ofbyte;F,r,h,m,st,ed,I,j,t,k,s,p,w:byte;G:array[1..10]ofbyte;e:array[L•8]of0.•1;c:array[1..8,1・・8]ofbyte;bb:Boolean;beginwriteCstart:J);readln(st);writeend/);readln(ed);fillchar(e,siz
6、eof(e),0);｛标记数组淸零｝filIchar(c,sizeof(c),0);｛路径数组清零｝f:=0;r:=1;L[r]:=st;h:=l;w:=l;bb:=true;whilebbdobeginh:=h+l;g[h]:=r+l;｛记录h+1层的首地址｝fori:=1towdobeginf:=f+l;m:=L[f];e[m]:=1;｛取队首结点,并设访问过标记｝fort:=1ton[m]do｛依次访问m结点的相邻结点｝ife[d[m,t]]=0then｛若m的相邻结点没有访问过｝beginr:=r+l;L[r]:=d[m,t];b[r]:=f;
7、｛则进队列｝end;end;w:=r+l-g[h];｛计算第h层的新结点数口｝s:=0;fork:二g[h]tordo｛检査第h层上的新结点是否存在廿标结点｝ifL[k]=edthen｛等于目标结点｝begins:=s+l；p:二b[k];j:二1;c[s,j]:=L[k]:whilepOldobeginj:=j+l;c[s,j]:=L[p]；p：=b[p];end;j:二j+l;c[s,j]:二L[p];fort:=jdownto1doift=lthenwriteln(c[s,t])elsewrite(c[s,t],，J);end;ifs<>0the
8、nbeginwritein(st,'一‘,ed,'total=，,s,'step二',jT)；
