7.3.1 深度优先搜索在线视频

同学们，大家好

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

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

不管对于何种数据结构，遍历都是最重要的操作

图的遍历也不例外

图的遍历是指，从图中某个顶点出发

访遍图中其余顶点，且使每一个顶点仅被访问一次

对图的遍历而言，除了要确定搜索策略之外

还有两个我们需要解决的问题

第一是如何确保每个顶点都被访问到

第二是 如何确保每个顶点只被访问一次

而不被重复的访问

图的遍历算法是求解图的连通性问题

拓扑排序和求关键路径等算法的基础

在讨论图的遍历之前，我们要先解决一个问题

求图中一个顶点的所有邻接点

假设已经用数组表示法实现了图的存储

求一个顶点的第一个邻接点和下一个邻接点的函数已经实现

可以用一个循环来实现求一个顶点的所有邻接点

观察for循环，首先调用求第一个邻接点函数

求顶点v的第一个邻接点

赋值给w，如果w大于等于0

说明第一个邻接点存在，循环中可能对邻接点进行某种处理

第一次循环结束后，调用求下一个邻接点函数

求v的w之后的下一个邻接点

赋值给w，如果下一个邻接点存在

继续循环，通过不断找下一个邻接点

可以循环找出v的所有邻接点

我们结合具体例子看一下

假设要找顶点v3的所有邻接点

那么参数v是2，调用FirstAdjvex(G, 2)

找出第一个邻接点是红圈对应的1

也就是顶点v2，顺便说一下

函数中的参数都是给顶点的存储位置

为例叙述方便，我还是直接说顶点的名字

对v2处理，调用NextAdjVex(G, 2, 1))

求v3的v2之后的下一个邻接点

从图上可以看出，下个邻接点是v4

下次循环继续求v3的v4之后的下一个邻接点是v5

再求v3的v5之后的下一个邻接点

v5之后没有邻接点了，函数返回-1

赋值给w，循环条件不成立，循环结束

完成求v3所有邻接点的过程

求一个顶点所有邻接点的操作对图遍历的实现非常重要

下面我们结合一个图例来讨论一下

深度优先遍历的搜索策略

深度优先遍历的过程，一般是从图中一个顶点开始

首先访问这个顶点，访问该顶点后

找它的邻接点，如果邻接点没有被访问过

则递归，从它的这个邻接点开始

再进深度优先

观察黑框中对从顶点v开始深度优先的描述

从顶点开始深度优先的函数是DFS

它有两个参数，第1个给出我们要遍历的图G

第2个给出这次深度优先的出发点v

DFS函数的意思是说

在图G中从顶点v开始行一次深度优先搜索

DFS函数中要做3个工作

第1个，我们称为做标记

前面说过，遍历中有一个问题

如何确保每个顶点只被访问一次

而不被重复的访问

采用的方法就是做标记

定义了一个和一维数组等长的标记数组visited

标记数组中的每一个单元对应一个顶点

遍历之前，标记数组全部初始化为0

表示所有顶点都没有被访问，遍历开始后

访问了一个顶点，就把标记数组中对应的单元置1

表示该顶点已经访问过了

第2个工作是访问顶点v

对顶点进行操作处理

第3个工作是循环找顶点v的所有邻接点

每次循环找出一个邻接点

找出邻接点w以后，进行判断

如果这个邻接点没有被访问过

递归调用DFS，从这个邻接点开始进行深度优先搜索

递归返回后，再找下一个邻接点

如果找到的邻接点访问过了，继续循环找下一个

下面我们就结合幻灯片上的图G4

具体看一下深度优先搜索的实现

这是一个有8个顶点的无向图

采用数组表示法实现其存储

我们从存在0号单元这个顶点v1开始进行深度优先遍历

调用DFS(G,0)

这层调用中，首先把标记数组中的0号单元置为1

做访问标记，表示已经访问过顶点v1了

随后呢，调用相关函数处理v1

接着就是第3步，循环找v1的邻接点

首先找v1的第1个邻接点

从存储结构上可以看到

v1的第一个邻接点是v2，v2没有访问过

递归DFS（G,1），从v2开始进行深度优先

图中用绿色虚箭头表示递归和返回

同样先给标记数组中1号单元做标记

访问v2，然后找v2的邻接点

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

循环继续找v2的v1之后的下个邻接点

是v4，v4没有被访问过

那么递归从v4开始进行深度优先

同样做标记，访问v4，找v4的邻接点

第一个邻接点v2访问过了

下一个邻接点v8没有访问过

递归从v8开始做深度优先，做标记

访问v8，8的第1个邻接点v4访问过了

然后随后找v8的v4之后的下一个邻接点

是v5，没有访问过，递归从v5开始做深度优先

做标记访问v5，v5的第1个邻接点v2访问过了

下一个邻接点v8也访问过了，for循环结束

找完v5的所有邻接点之后

就是说从v5不能继续再向前搜索了

DFS(G,4)这层递归结束，返回到v8这层递归

继续循环求v8的v5之后的下一个邻接点

v8没有下一个邻接点了，那么v8这层递归结束

返回到v4

v4在v8之后也没有邻接点了

返回到v2

在v2中继续找v4后的下一个邻接点

找到v5，已经访问过了， v5之后没有下一个邻接点

返回v1。继续找v1的v2之后的下一个

是v3

后续的递归遍历过程就不重复了

从v3返回以后，v1没有下一个邻接点了

从v1返回，完成了对这个图的遍历

下面我们看一下深度优先遍历算法的实现

首先声明标记数组

随后，定义了一个指向函数的指针VisitFunc

遍历中通过函数指针调用函数来处理我们访问到的顶点

下面是函数DFS的定义，前面已经详细讨论过了

这里就不重复了

DFS是从图中一个顶点出发进行深度优先搜索

但它并不是图的遍历算法

因为它不能保证，访问到图中的每个顶点

我们观察一下幻灯片上的图

这是一个无向图

但是它不是一个连通图

如果DFSs从v1开始搜索

实际上只能访问到v1所在的联通分量

无法访问v3，v6，v7这三个顶点

图的遍历函数是DFSTraverse

函数有两个参数，一个是要遍历的图

一个是指向函数的指针visit

先把visit复制给全局变量的函数指针visitfunc

后面访问顶点时，直接调用visitfunc处理顶点

DFS递归时，函数指针不必作为参数传递了

第一个for循环完成对visit的初始化

把标记数组的单元置为false，也就是0，表示

所有顶点都没有被访问过

第二个for循环是考察图中的每一个顶点

如果这个考察到的顶点，没有被访问过

就从这个顶点开始再调用DFS

进行深度优先搜索，通过这个循环

就可以保证遍历图中所有的顶点

好，同学们，关于图的深度优先搜索

我们就讨论到这，下次课再见