简介

基本思想

广度优先遍历的性质

算法实现

与深度优先遍历的比较

报告(1.调试 2.测试用例运行结果)

简介

广度优先遍历是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

基本思想

1、 从图中某个顶点V0出发，并访问此顶点；

2、 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；

3、 重复步骤2，直到全部顶点都被访问为止。

广度优先遍历的性质

与深度优先遍历类似，广度优先遍历也有许多有用的特性：

1、广度优先生成树

在广度优先遍历中，如果将每次“前进”（纵深）路过的（将被访问的）结点和边都记录下来，就得到一个子图，该子图为以出发点为根的树，称为广度优先生成树。这种情况与深度优先遍历类似。

类似地，也可以给广度优先生成树结点定义时间戳。

2、最短路径

显然，从v0出发广度优先遍历图，将得到v0到它的各个可达到的路径。我们这里定义路径上的边的数目为路径长度。与深度优先遍历不同，广度优先遍历得到的v0到各点的路径是最短路径（未考虑边权）。

算法实现

template <int max_size>

void Digraph<max_size> ::

breadth_first(void (*visit)(Vertex &)) const

/* Post: The function *visit has been performed at each vertex of the Digraph in breadth-first order.

Uses: Methods of class Queue. */

{

Queue q;

bool visited [max_size];

Vertex v, w, x;

for (all v in G) visited [v] = false;

for (all v in G)

if (!visited [v]) {

q.append (v);

while (!q.empty ( )){

q.retrieve (w);

if (!visited [w]) {

visited [w] = true; (*visit) (w);

for (all x adjacent to w) q.append (x); }

q.serve ( ); } }

}

广度优先搜索算法pascal 算法框架

Program BFS;

初始化，存储初始状态（记录初始结点）；

设队列首指针closed=0；队列尾指针open：=1；

repeat

首指针closed后移一格，取其所指向的结点；

for r:=1 to max_r do

begin

if子结点符合条件 且 子结点没有重复扩展 then

begin

尾指针open加1；把新结点存入队列尾；

记录相关信息；

if 达到目标 then 输出且结束；

end;

until closed>=open(队列空)

与深度优先遍历的比较

广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。

深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。

广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。

可以看到两种方法最大的区别在于前者从顶点的第一个邻接点一直访问下去再访问顶点的第二个邻接点；后者从顶点开始访问该顶点的所有邻接点再依次向下，一层一层的访问。

报告

1.调试

一、 队列操作中，若队列中只有一个元素，删除队头元素时产生错误。原因是程序中没有考虑这种特殊的情况。修改后，队列的删除操作运作正常。

二、在求图的第u个顶点，与其相邻的一系列顶点中，第w个顶点的下一个顶点时，若是求最后一个顶点的下一个顶点时，函数进入了死循环。原因是判断条件没有写好，造成了判断值恒为真，因此进入了死循环。修改后，函数正常运行。

三、广度优先遍历图的时候，是从指定的任一顶点开始遍历，当遇到该图为无向非连通图，并不能把该图遍历。

原因是没有写出一个循环体，去尝试遍历其他没有被遍历的顶点。加上这样一个循环体后，便可以遍历任意一种图了，并且还可以在此基础上算出图的两通分量。

四、在输入图信息的时候，若输入非法字符，程序会异常终止。例如程序要求输入一个整型，用户却输入了一个字母，这时候会出现异常。只是程序是否健壮性的一个体现。采用输入流的一些函数，便可以解决这一问题。还有其他一些类似的输入异常，都是采用类似的处理方法。

五．作为一个完整的程序，友好的界面是必须的。因次程序中适当地采用系统中的清屏命令，使得界面更加简洁，明了。

2.测试用例运行结果

一、输入图的顶点数：a，运行结果：非法输入，请重新输入。

二、确定第1个顶点与第2个顶点是否有关系时，输入非0和1，运行结果：程序并不响应。

三、确定从第几个顶点开始遍历该图是，输入：j，r，ab，-1，0，1，21.

四、运行结果：非法输入，请重新输入。