下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 队列的应用BFS

队列的应用BFS.ppt

队列的应用BFS

hellojj
2010-10-27 0人阅读 举报 0 0 暂无简介

简介:本文档为《队列的应用BFSppt》,可适用于考试题库领域

保定二中NOIP数据结构队列的应用网络中心刘中一wwwnoibdezcnQQ:队列(FIFO)队列的定义所谓队列就是允许在一端进行插入在另一端进行删除的线性表。允许插入的一端称为队尾。规则:先进先出!初始化一般头:open=尾:closed=队列头open队列尾closed当open>=closed时,队列空非空:open<closed队列数组a下标:……我们按照如下方式定义队列:Constm=队列元素的上限Varq:array…mofinteger{定义队列}openclosed:integer{队尾指针和队首指针}、队列的基本运算队列的运算主要有两种:入队(ADD)和出队(DEL)、过程ADD(x)在队列q的尾端插入元素xprocedureADD(x:qtyper)begin{后移队尾指针并插入元素x}closed:=closedqclosed←xend{ADD}注意:实际操作可以不使用过程!、函数DEL取出q队列的队首元素functionDELbeginopen:=opendel:=qopenend{DEL}注意:实际操作可以不使用过程!例:  一矩形阵列由数字到组成,数字到代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。输入:整数m,n(m行n列)矩阵输出:细胞的个数。样例:输入:输出:共个细胞算法步骤:、从文件中读入m*n矩阵将其转换为、矩阵存入pic数组中、沿pic数组矩阵从上到下从左到右找到遇到的第一个细胞将细胞的位置入队h并沿其上、下、左、右四个方向上搜索如果遇到细胞(picI,j=)则将其位置入队入队后的位置picI,j数组置为、将h队的队头出队沿其上、下、左、右四个方向上搜索如果遇到细胞则将其位置入队入队后的位置pic数组置为、重复直至h队空为止则此时找出了一个细胞、重复直至矩阵找不到细胞、输出找到的细胞数。constdx:arrayof=(,,,)dy:arrayof=(,,,)vars:stringpic:array,of{:无细胞:有细胞}m,n,i,j,num:integerh:array,ofbyte{队列:存细胞的坐标:行:列}proceduredoing(i,j:integer)vark,open,closed,x,y:integerbegininc(num)pici,j:=open:={队列头}closed:={队列尾}h,:=ih,:=j{遇到的第一个细胞入队}whileopen<closeddo{队不空}begininc(open)fork:=todo{沿细胞的上下左右四个方向搜索细胞}beginx:=hopen,dxky:=hopen,dyk{进入位置(xy)}if(x>)and(x<=m)and(y>)and(y<=n)and(picx,y=){(x,y)处有细胞}thenbegininc(closed){进队列}hclosed,:=xhclosed,:=ypicx,y:={打删除标志}end{为细胞的入队}endendbeginfillchar(pic,sizeof(pic),)num:=fillchar(h,sizeof(h),)assign(input,'ain')reset(input)assign(output,'aout')rewrite(output)readln(m,n)fori:=tomdobeginreadln(s)forj:=tondoifsj=''thenpici,j:=elsepici,j:=endfori:=tomdoforj:=tondoifpici,j=thendoing(i,j){在矩阵中寻找细胞}writeln(num)close(input)close(output)end在深度优先搜索算法中是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索本层的结点没有搜索处理完时不能对下层结点进行处理即深度越小的结点越先得到扩展也就是说先产生的结点先得以扩展处理这种搜索算法称为广度优先搜索法。英语中用BreadthFirstSearch表示所以我们也把广度优先搜索法简称为BFS。广度优先搜索BFS从图中某一顶点Vo出发首先访问Vo相邻的所有未被访问过的顶点V、V、……Vt再依次访问与V、V、……Vt相邻的且未被访问过的所有顶点。如此继续直到访问完图中所有的顶点。如果用广度优先法对下图中结点进行搜索从结点V出发先搜索处理它的子结点V和V即深度为的结点然后搜索深度为的子结点V、V、V、V最后搜索深度为的结点V和V。整个搜索的次序与结点产生的次序完全一致。广度优先搜索的基本思想深度VVVVVVVVV)从某个顶点出发开始访问被访问的顶点作相应的标记并输出访问顶点号)从被访问的顶点出发依次搜索与该顶点有边的关联的所有未被访问的邻接点并作相应的标记。)再依次根据)中所有被访问的邻接点访问与这些邻接点相关的所有未被访问的邻接点直到所有顶点被访问为止。广度优先搜索基本算法procedurebfs(i)beginwrite(i){输出第一个点}vi:=true{表示被访问}insert(q,i){q是队列i进队}repeatk:=delete(q){出队}forj:=tondoif(ak,j=)and(notvj)thenbeginwrite(j)vj:=trueinsert(q,j)enduntil队列q为空广度优先搜索基本算法广度优先搜索基本算法例图的广度优先遍历如下图找出C到C的一条最短路径并求出其路程总长度(采用广度优先搜索的顶点访问序列为C,C,C,C,C,C)。例图的广度优先遍历vara:array,ofinteger图数组v:arrayofinteger表示是否访问过q:arrayofinteger队列i,j,k,n:integeropen,closed:integer队列首尾例图的广度优先遍历例图的广度优先遍历procedurebfs(x:integer)vari,j:integerbeginfillchar(v,sizeof(v),)fillchar(q,sizeof(q),)write(x,‘’)vx:=第一个点正常输出open:=closed:=qclosed:=x第一个点进入队列repeatinc(open)i:=qopen对头出队forj:=tondo遍历与I相邻的点if(ai,j=)and(vj=)thenbeginwrite(j,‘’)vj:=输出本层的所有点inc(closed)qclosed:=j发现与I相邻则队尾入队enduntilopen>=closed队空结束end例图的广度优先遍历例图的广度优先遍历beginreadln(n)fori:=tondobeginforj:=tondoread(ai,j)readlnendbfs()end例图的广度优先遍历例图的广度优先遍历例请课下完成例请课下完成八数码难题(Eightpuzzle)。在X的棋盘上摆有个棋子在每个棋子上标有~中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是给出一种初始布局(初始状态)和目标布局(目标状态)找到一种最少步骤的移动方法实现从初始布局到目标布局的转变。初始状态和目标状态如下:初始状态目标状态求解本题我们可以分步进行。谢谢!现在是提问时间

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/23

队列的应用BFS

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利