宽度优先搜索48415

1、宽宽 度度 优优 先先 搜搜 索索安庆四中安庆四中 丁贤友丁贤友一、队列一、队列l队列是先进先出的线性表，它仅允许在表的后端进行插入操作，在表的前端进行删除操作。queue1queue2queuen出队出队队头队头队尾队尾入队入队队列操作队列操作 l在设计队列的常用操作时，用front指针控制队头，每次从队列中移出一个queuei时，置front增长1，使得队头指针往后移一位；用rear指针控制队尾，每插入一个queuei,置rear增长1；初始时，队列为空，front、rear都为0。队列的常用操作有入队、出队、判空等操作。lfront:对头指针，指向实际队头元素的前一个位置lrear: 队

2、尾指针，指向实际队尾所在的位置队列定义队列定义l队列的定义lMaxsize=队列中元素的上限；lType l queue=recordl data:array1.maxsize of datatype;l front,rear:0.maxsize;l end;lVar q:queue;队列操作队列操作l初始化队列过程lProcedure qcreate(var q:queue);l begin q.front:=0; q.rear:=0 end;l判断队列是否为空lFunction qempty(q:queue):boolean;l begin qempty:=(q.front=q.rear)

3、; end;l判断队列是否为满lFuntion qfull(q:queue):boolean;l begin qfull:=(q.rear=maxsize); end;队列操作队列操作l入队过程lProcedure inqueue(var q:queue; x:datatype);l beginl if qfull(q) then writeln(queue is full!);l else beginl inc(q.rear);l q.datarear:=x;l end;l end;队列操作队列操作l出队过程lProcedure outqueue(var q:queue; var x:dat

4、atype);l beginl if qempty(q) then writeln(queue is empty)l else beginl inc(q.front);l x:=q.dataq.front;l end;lEnd;例题例题1：BFSl给定一张给定一张N个顶点、个顶点、E条边的无向图，请用条边的无向图，请用BFS从顶点从顶点1遍历这张图。遍历这张图。l输入文件：输入文件：l第一行为第一行为N、E，意思如题意；，意思如题意；l以下以下E行，每行行，每行2个整数，代表个整数，代表2个顶点的编号，表示他们之间有边个顶点的编号，表示他们之间有边连接。连接。l输出文件：输出文件：l输出一行，

5、从顶点输出一行，从顶点1广搜的顶点的编号，用空格隔开。广搜的顶点的编号，用空格隔开。l输入样例：输入样例：l6 5l1 2l1 3l2 4l输出样例：输出样例：l1 2 3 4 5 6【分析【分析】lBFS的原理为从源点出发，先搜索出所有与源点相连接的点，再搜索出与这些点相连的其它点，它是逐层遍历出所有与源点相连的点。这种原理恰好与队列的先进先出相吻合，可以用队列实现BFS。分以下3个步骤来实现：l初始时，顶点1入队，并输出顶点1；l判断队列是否为空，不为空时，取出队首元素queuefront,再将与队首元素相连的所有顶点入队，并都输出；l重复操作，直至队列为空。l当顶点比较多时，队列易出现假

6、溢出情况，可以用循环队列来实现。在存储队列的数组中，用front、rear两个指针控制首位元素。lProcedure bfs(i:longint);l front 0; rear 1; queuerear i; write(i, );l flagi true;l while frontrear dol beginl inc(front); tmp queuefront;l for j 1 to n dol beginl if (not flagj) and pathtmp,j=1 thenl beginl write(j, ); inc(rear); queuerear j;l flagj t

7、rue;l end;l end;l end;广广 搜搜l广搜又叫广度优先搜索。它是从源点出发，逐层搜索出所有的点。广搜一般用在求最少步数的情况，由于它的逐层特性，它能保证搜到最小或最少的解。例例2：找目标：找目标l给定一幅给定一幅nn的图，图中有的图，图中有.，#和和* ，*代表起代表起点，点， #代表目标点，从起点到目标点走时，只能向上、代表目标点，从起点到目标点走时，只能向上、下、左、右四个方向走，每次只能走一步，且不能走斜线。下、左、右四个方向走，每次只能走一步，且不能走斜线。问从起点，经过最少几步，能到达目标点。问从起点，经过最少几步，能到达目标点。l输入数据：输入数据： nn的地图的

8、地图l输出数据：最少的步数。输出数据：最少的步数。l输入样例输入样例l. . . .l. * . .l. . . .l. . . #l输出样例：输出样例：l4【分析【分析】l题目要求，从源点出发，以最少的步数到达目标点，如果用深搜的话，需要搜索出所有可行方案，找出其中步数最少的点；用广搜的话，从源点开始，逐层拓展，找到目标点时，即为 最少的步数。广搜算法实现时，可以用队列来存储拓展出来的每层状态。l算法实现时，用算法实现时，用dx，dy一维数组预存一维数组预存4个拓展方向的个拓展方向的x，y坐标的增量，用坐标的增量，用disti,j数组记录到达数组记录到达i，j点的步数，用点的步数，用si,j

9、数组记录每个点的初始状态，用队列数组记录每个点的初始状态，用队列q记录入队、出记录入队、出队情况。队情况。ldx:array1.4 of longint=(0,0,1,-1);ldy:array1.4 of longint=(1,-1,0,0);lTnode=record x,y:longint end; lDist:array0.205,0.205 longint; lS:array0.205,0.205 of char; /记录每个点的初始状态记录每个点的初始状态lq:array0.205*205 of tnode; /用队列存储用队列存储广搜过程如下：广搜过程如下：lProcedure bfs;l fillchar(dist,sizeof(dist),-1);ldistx0,y0:=0;lh0； r1；lqr.x x0; qr.y y0; /起点入队起点入队lwhile (h=1) and (xx=1) and (yy=n)l and d