7.3.2 广度优先搜索在线视频

同学们，大家好

我是云南大学信息学院教师孔兵

这节课我们讨论图的第二种遍历策略---广度优先搜索。

我们仍然结合图G4来讨论广度优先搜索策略

搜索仍然是从图中某一个顶点出发进行

基本的策略是，首先访问出发的顶点

随后访问该顶点的所有邻接点，再访问

邻接点的邻接点，依次进行下去

广度优先遍历有明显的层次特性

结合图G4看一下，如果从v1开始进行广度优先搜索

访问的次序是先访问v1，随后访问v1的邻接点v2v3

再访问v1的邻接点的邻接点，v 4 v 5 v 6 v 7.最后访问v8

那么在广度优先搜索当中，我们要考虑的主要问题是

怎么保证按照这样一个层次次序来搜索图中的顶点

这里就要用到前面学习过的数据结构—队列

队列最重要的特点是，所谓先进先出

我们正是利用队列的这个特性

完成按层次的对图的遍历

下面结合图例介绍一下广度优先的搜索过程

搜索中仍然利用一个标记数组

作为顶点是否访问的标志

观察一下幻灯片中的伪代码

这是广度优先搜索主要的代码段

如果从v1开始进行广度优先搜索

那么，首先访问v1，做标记

随后Enqueue(Q,0)，把v1顶点入队列

队列中第一个入队列的是0

随后进入单循环

当队列不空的时候进行循环

循环中，首先队头元素出队列

现在队头元素是0，队头元素用u带回来

循环考察u的所有邻接点，考察过程中

如果被考察的顶点没有访问过

则该顶点做访问标记，访问该顶点

把该顶点的Enqueue入队列，例子中u=0

我们考察v1的邻接点

v1有两个邻接点v 2 v 3

这两个邻接点都没有被访问过

做标记，访问，入队列

现在队列中有1和2两个元素

回到while循环，队列不空，队头元素1出队列

随后循环考察v2的所有邻接点

v2的第1个邻接点是v1，已经访问过了

第2个是v4，第3个是v5，都没有访问过

做标记，访问，入队列

后续过程相同，就不重复了

通过实例大家看到，利用队列

保证了按照这样一层一层的次序对图进行遍历

也就是广度优先搜索

图G4是一个连通图

从任意顶点出发都可以遍历图中所有顶点

下面我们看一下广度优先搜索算法的实现

广度优先搜索算法是BFSTraverse，有两个参数

一个是要遍历的图，一个是指向函数的指针

一般用该指针所指函数对正在访问的顶点进行处理

第一个for循环是对标记数组做初始化

随后对我们要用到的队列Q也做一个初始化

为后续使用做好准备

第一个黄色框中的for循环是对所有顶点进行考察

它的作用是处理从一个顶点出发不能遍历所有顶点的问题

这点和深度优先搜索中的一样

考察到顶点v的时候，如果v被访问过了

循环，继续考察下一个顶点

如果v没有被访问过，把v的标志置为真

访问顶点v，把顶点v入队列

下面绿色while循环这段代码

我们结合例子已经详细讨论过了

通过这段代码可以访问到所有从顶点v有路径可达的顶点

队列空时，说明这样的顶点已经被访问完了

回到for循环考察后续顶点，for循环完成后

图中所有顶点都被访问了，广度优先搜索结束

前面讨论二叉树的遍历的时候

我们留下过一个问题

二叉树除了先序中序后序的遍历策略以外

还有层序的遍历策略，这里我们学习了广度优先遍历

请大家课后认真思考一下，借助广度优先搜索的思路

怎么实现二叉树和树的层序遍历

下面我们讨论一下图的连通性的问题

判别无向图是否连通的算法，是基于图的遍历算法

无向图的连通分量和生成树

如果是连通图，根据前面遍历的示例可以看到

从任意顶点出发一次遍历

便可以访问到图中所有的顶点

如果是非连通图的话

需要从多个顶点出发来遍历

每次从一个顶点的遍历

可以访问到这个顶点所在的连通分量

深度优先生成树和广度优先生成树的概念

设E(G)为连通图G中所有边的集合

则从图中任一顶点出发遍历图时

必定将 E(G)分成两个集合T(G)和B(G)

其中 T(G)是遍历过程中经历的边的集合

B(G)是剩余边的集合

显然， T(G)和图G中的所有顶点一起构成

连通图G的极小连通子图，也就是生成树

根据遍历的策略分别称为

深度优先生成树和广度优先生成树

从深度优先生成树和广度一些生成树的定义来看

主要是说遍历，因为是连通图

从任意顶点开始遍历

必定能访问图中所有顶点

这里强调的主要是这样的一个遍历过程中

会把边的集合E(G)，分为两个集合T(G)和B(G)

其中，T(G)是遍历过程中经历的边的集合

这些经历的边和顶点一起就构成了一颗生成树

那么什么叫遍历过程中经历的边呢？

下面我们通过一个实例来直观的看一下

我们仍然以图G4为示例

所谓遍历过程中经历的边是指

在遍历的过程当中

通过该边找到了一个未被访问过的顶点

这样的边才是遍历过程中经历的边，属于T(G)

看一下深度优先生成树，红色的边就是经历过的边

假设我们从v1开始深度优先搜索

那么通过v1到v2这条边

找到了顶点v2，v2没有被访问过

这条边是经历过的边

从v2到v4这条边找到v4

从v4到v8这条边找到v8

从v8到v5这条边，找到了v5

通过这4条边，都找到了未被访问过的顶点

而v5到v2这条边，因为v2已经被访问过了

所以通过它没有找到未被访问过的顶点

它就不是遍历过程中经历的边

其它边的情况类似

连通图中，从一个顶点出发可以访问到所有顶点

也就是其余n-1的顶点

那么，在遍历过程中

必然是通过n-1条边找到这n-1个顶点

经历过的边有n-1条，这些边就和所有顶点一起

构成了一颗生成树

因为，是按深度优先策略搜索的

这就是一棵深度优先生成树

广度优先生成树类似，因为遍历策略不同

发挥作用的边是不一样的

二者的生成树也就不同

对于非连通图来说的话呢

每个连通分量中的顶点

和遍历时经历的边一起

构成若干颗生成树

这些连通分量的生成树组成非连通图的生成森林

好同学们，这节课我们就讲到这儿

下次课再见