宽度优先搜索48415

《宽度优先搜索48415》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、的位置队列定义队列的定义Maxsize=队列中元素的上限；Typequeue=recorddata:array[1..maxsize]ofdatatype;front,rear:0..maxsize;end;Varq:queue;队列操作初始化队列过程Procedureqcreate(varq:queue);beginq.front:=0;q.rear:=0end;判断队列是否为空Functionqempty(q:queue):boolean;beginqempty:=(q.front=q.rear);end;判断队列是否为满Funtionqfull(q:q

3、ueue):boolean;beginqfull:=(q.rear=maxsize);end;队列操作入队过程Procedureinqueue(varq:queue;x:datatype);beginifqfull(q)thenwriteln(‘queueisfull!’);elsebegininc(q.rear);q.data[rear]:=x;end;end;队列操作出队过程Procedureoutqueue(varq:queue;varx:datatype);beginifqempty(q)thenwriteln(‘queueisempty’)else

4、begininc(q.front);x:=q.data[q.front];end;End;例题1：BFS给定一张N个顶点、E条边的无向图，请用BFS从顶点1遍历这张图。输入文件：第一行为N、E，意思如题意；以下E行，每行2个整数，代表2个顶点的编号，表示他们之间有边连接。输出文件：输出一行，从顶点1广搜的顶点的编号，用空格隔开。输入样例：65121324输出样例：123456【分析】BFS的原理为从源点出发，先搜索出所有与源点相连接的点，再搜索出与这些点相连的其它点，它是逐层遍历出所有与源点相连的点。这种原理恰好与队列的先进先出相吻合，可以用队列实现BFS。

5、分以下3个步骤来实现：①初始时，顶点1入队，并输出顶点1；②判断队列是否为空，不为空时，取出队首元素queue[front],再将与队首元素相连的所有顶点入队，并都输出；③重复②操作，直至队列为空。当顶点比较多时，队列易出现假溢出情况，可以用循环队列来实现。在存储队列的数组中，用front、rear两个指针控制首位元素。Procedurebfs(i:longint);front←0;rear←1;queue[rear]←i;write(i,’‘);flag[i]←true;whilefront

6、front];forj←1tondobeginif(notflag[j])andpath[tmp,j]=1thenbeginwrite(j,’’);inc(rear);queue[rear]←j;flag[j]←true;end;end;end;广搜广搜又叫广度优先搜索。它是从源点出发，逐层搜索出所有的点。广搜一般用在求最少步数的情况，由于它的逐层特性，它能保证搜到最小或最少的解。例2：找目标给定一幅n×n的图，图中有’.’，’#’和’*’，’*’代表起点，’#’代表目标点，从起点到目标点走时，只能向上、下、左、右四个方向走，每次只能走一步，且不能走斜线。问

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

8、[1..4]oflongint=(0,0,1,-1)