队列的应用76427

队列的应用(宽搜)宽度优先搜索算法算法：宽度优先搜索算法(又称广度优先搜索算法)是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta 单源最短路径算法和Prim最小生成树算

队列的应用(宽搜) 宽度优先搜索算法算法： Dijksta 宽度优先搜索算法(又称广度优先搜索算法)是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。单源最短 Prim 路径算法和最小生成树算法都采用了与宽度优先搜索类似的思想。 宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再 用产生 式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符 逐一扩展第二层 所有结点……，如此依次扩展，直到发现目标结点为止。 宽度优先搜索基本算法如下： list[l]:=source; list ｛加入初始结点，为待扩展结点的表｝ head:=O; ｛队首指针｝ foot:=l; ｛队尾指针｝ REPEAT head:=head+l; FOR x:=l to DO 规则数 BEGIN nw; 根据规则产生新结点 IF not_appear(nw,list) THEN ｛若新结点队列中不存在，则加到队尾｝ BEGIN foot:=foot+l; list[foot]:=nw; list[foot].father:=head; IFlist[foot]THEN =目标结点输出； END ； END ； UNTIL head>foot; (队列为空表明再无结点可扩展｝ 例一矩形阵列由数字到组成,数字到代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一 细胞,求给定矩形 1： 0919 阵列的细胞个数。 如:阵列 0234500067 1034560500 2045600671 0000000089 有个细胞。 4 算法步骤： 从文件中读入矩阵阵列，将其转换为矩阵存入数组中； 1.m*nbooleanbz 沿数组矩阵从上到下，从左到右，找到遇到的第一个细胞； 2-bz 3 将细胞的位置入队并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置数组置为 .h,bzFLASE； 4 将队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置数组置为 .hbzFLASE； 5 重复直至队空为止，则此时找出了一个细胞； .4,h 6 重复直至矩阵找不到细胞； .2, 7 输出找到的细胞数。程序： . program xibao; const dx: array [1.. 4] of -1.. 1=(-1, 0, 1, 0); dy:array[1.. 4] of -1.. 1=(0, 1, 0, -1); var int:text; name, s:string; pic:array[1.. 50, 1.. 79] of byte; bz:array[1.. 50, 1.. 79] of boolean; m, n, i, j, num: integer;