宽度优先搜索算法_第1页
宽度优先搜索算法_第2页
宽度优先搜索算法_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

广度优先搜索广度优先搜索广度优先搜索类似于树的按层次遍历的过程。它和队有很多相似之处，运用了队的许多思想，其实就是对队的深入一步研究，它的基本操作和队列几乎一样。三、队和广度优先搜索的运用图4表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。图4分析：看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。如图5。ABcDEFGHA10001011B01111011C01100111D01011101E11011100F00111110G11100110H11110001图5首先想到的是用队的思想。我们可以a记录搜索过程，a.city记录经过的城市,a.pre记录前趋元素，这样就可以倒推出最短线路。具体过程如下：（1） 将城市A入队，队首0、队尾都为1。（2） 将队首所指的城市所有可直通的城市入队（如果这个城市在队中出现过就不入队，可用一个集合来判断)，将入队城市的pre指向队首的位置。然后将队首加1,得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。以下为参考程序：constju:array[1..8,1..8]ofinteger=((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));typer=record｛记录定义｝city:array[1..100]ofchar;pre:array[1..100]ofinteger;end;varh,d,i:integer;a:r;s:setof'A'..'H';procedureout;｛输出过程｝beginwrite(a.city[d]);repeatd:=a.pre[d];write('—',a.city[d]);untila.pre[d]=0;writeln;halt;end;proceduredoit;beginh:=0;d:=1;a.city[1]:='A';a.pre[1]:=0;s:=['A'];repeat｛步骤2｝inc(h);｛队首加一，出队｝fori:=1to8do｛搜索可直通的城市｝if(ju[ord(a.city[h])-64,i]=0)and(not(chr(i+64)ins))then｛判断城市是否走过｝begininc(d);｛队尾加一，入队｝a.city[d]:=chr(64+i);a.pre[d]:=h;s:=s+[a.city[d]];ifa.city[d]='H'the

人人文库> 全部分类> 行业资料 > 机电工程

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论