当前课程知识点：数据结构 > 第6章 图 > 6.3 遍历 > 讲解（上）
本节，我们来学习图的遍历
先看第一种遍历方式
深度优先搜索
简称DFS
我们首先访问给定的起始顶点v
然后，重复以下过程
直到图当中所有顶点都访问完毕
我们访问v的首个未被访问过的邻居w
然后，再去访问w的首个未被访问过的邻居
并如此下去
在访问过程当中
如果某一个顶点
它的所有的邻接点，都已经被访问过了
这时候，我们应该回退到最后一次访问的那个顶点
然后，从这个顶点开始
再重复刚才的过程
比如，现在给定的起始顶点v是1
那我们从1开始，走1到2这条边
然后，走2到4这条边，注意，我们前面讲过
在图当中
所有顶点的地位，都是一样的
一个顶点的多个邻居之间
实际上是没有先后、左右区分的
我们在这里认为，2是1的第一个邻居，是因为，1的两个邻居2和3
我们通常认为编号小的那个
是它前面的邻居
这只是一种约定
1到2，2到4
然后，4到8
大家看到，我们是优先朝着纵深方向去访问
顶点的
这也是深度优先搜索，它的名称的由来
8完了之后，到5
5访问完了之后
注意，2已经被访问过了
那么，回到上一次访问的顶点8，去访问它的下一个未被访问过的邻居
是6，然后，6到3
3的邻居1，已经被访问过了
应该走3到7
这条边，到7
现在，这8个顶点，都已经被访问完了
得到的序列就是1、2、4、8、5
6、3、7
我们再来看一个有向图，同样，给定的起始
顶点是1
从1经历这条边，到2
再经历这条边，到4
再经历这条边，到8，8是到不了5的，这时候
我们要回退到8
8的邻居都访问完了
再回退到4，再回退到2，回退到1，下一个邻居到3
3到6
6到7
注意，6到7，走的是这条边
而不是这条边
现在，我们发现一个问题
从1开始，永远到不了5
那意味着，我们将来在写算法的时候
要考虑到这种极端的边界情况
5这个顶点
实际上，要放在最后单独地去访问，我们从1开始，只能访问到这几个顶点，5是访问不到的
我们回顾一下刚才的过程，图的DFS，也就是深度优先搜索，它实际上跟树的先序遍历是对应的
大家想一下，树的先序遍历
永远是先访问根
访问根之后，再去访问左子树的根
然后，再去访问左子树的左子树的根
它也是优先朝着纵深方向去访问的
接着，我们来看几个问题
如何确定某一个顶点是否被访问过了，很简单
我们只需要引入一个一维数组，它的长度，跟顶点个数是一样
用它的0和1，来标志未被访问和已被访问，visited这个数组
第二个问题是，如何找到顶点的邻居
也就是邻接点
这个主要取决于
图是用什么方式来存的
比如，我们现在以邻接矩阵为例
这是我们想表示的图
这是在内存当中的邻接矩阵，我们现在先不看
这里逻辑上的图
我们只看内存
根据这个邻接矩阵
如何来找到邻接点呢？假设
这里0、1、2、3分别表示
A、B、C、D这4个顶点
它们的下标，我们给定的起始顶点v是A
从A开始，访问它
然后，找它的邻居，扫描这一行
因为是无向图，扫描这一行
这一列，都可以，发现B这一列是1
于是到B
到了B之后，应该扫描B这一行
因为是深度优先
从B开始，找它的第一个邻居
发现D这一列是1
于是到D
然后，看D这一行，这一列是B，已经访问过了，回到它
因为刚才是从A到B
然后，B到D的
D的邻居都被访问完了
我们应该回到B，B的邻居也被访问完了
我们回到A
下一个邻居是C
所以，D之后是C
是这样得来的
如果我们采用邻接表呢
类似地，我们从A开始
因为这里是无向图
A到B有一条边
所以到B，再从B这个链表开始
这个实际上是B到A之间的边
已经被访问过了
下一条边
3代表着D
所以是D
D的邻居B，已经被访问过了，回退
回到这里，再回退
两个邻居都访问完了
再回退，到A
那么，下一个邻居是C
所以，最后是C
无论是邻接矩阵，还是邻接表
找邻居
都还是比较方便的
现在，我们来看深度优先搜索的算法实现
我们刚才给出的算法思想
实际上已经包含了递归的步骤
原问题
是从v开始，做深度优先搜索
访问v的第一个邻居w之后
下面要做的事情，是从w为起始顶点，开始做DFS
一直到某一个顶点
它的所有邻居，都被访问过了
或者说，这个顶点没有未被访问过的邻居
这时候，就是递归的终结条件
现在，我们给出具体的算法
首先，visited这个数组它的长度，就是顶点的容量
里面每一个值都是0
我们遍历图G
它是以邻接矩阵表示的，做深度优先搜索，起始顶点是v
我们首先访问v，把它的自身信息打印出来
然后，把相应的visited元素置成1，表示
v这个顶点被访问过了
然后开始做循环，这个循环
它的第一个条件，是firstAdjVert，在G当中
找顶点v的第一个邻居
这个邻居的下标
我们作为返回值，赋给w，这个for循环
它的第二个表达式，是w大于等于0
那意味着，这个伪码
当v
没有首个邻居的时候
它返回一个负值
以便让这里的w小于零
让循环结束
v的第一个邻居
我们先判断一下，它是否被访问过了
如果它已经被访问过了
我们就不需要访问了
如果没有被访问过
也就是visited[w]是0
那么，开始递归
同样是遍历相同的图
但是，起始顶点不一样
原来是v
现在是w
这次递归结束之后，for循环的第三个
表达式，是nextAdjVert，去找图G中v的下一个邻居，把返回值赋给w
这里第三个参数是什么意思呢
为什么找下一个邻居需要
第三个参数呢
这是因为，找一个顶点的多个邻居当中的下一个，总要告诉我
当前访问的邻居是谁
所以，第三个参数代表着当前
访问的邻居
或者说，上一次访问的邻居
只有这样
才能找到v的下一个邻居
同样，w没有访问过
那么，以它为起始顶点，做深度优先
现在，看起来算法已经写完了
但是别忘了，有一些顶点
从给定的起始顶点开始，是没法直接访问到的
比如，刚才那个有向图当中的5顶点
所以
为了
算法能够正确地访问所有的顶点
必须考虑一些极端情况
这里
有一个大写的DFS
这是我们最终的算法
它调用了刚才的小写的dfs
它做的事情很简单
就是以图G当中每一个顶点开始，从0遍历顶点个数次，v++
以图G当中每一个顶点(为起始顶点)，分别去调用上面的小写的dfs这个深度优先搜索
这个循环，它的意义就是防止
一个图当中
某些顶点，是永远没法被访问到这样一种极端的情况
这个算法
它的时间复杂度是多少呢
根据你所采用的存储方式不同而不同
如果你采用邻接矩阵
因为，这个算法总体上是递归，递归程序
基本步骤的重复次数，是比较难以分析的
但是，我们可以采用一些简单的办法
比如，像这一行printf语句，它一共要进行多少次呢
它肯定是执行n次
因为有n个顶点
在递归的时候
像这样的伪码去找邻居
很明显
我们去找邻接矩阵当中，某一个顶点的邻居
去扫描某一行的n列值，就可以了
所以
以邻接矩阵存放，这个算法
它的时间复杂度就是n*n
如果你采用邻接表来存放，一样的
对于邻接表，只有当顶点未被访问的时候
才会去访问
以这个顶点为头结点的单链表
那么，n个顶点就会访问n次
每一个单链表当中
用来表示边的结点数
是不知道的
但总体是知道的，所有的单链表中，用来表示边的结点数，一定是e
所以，从这个角度来说
总的时间复杂度，采用邻接表来存放
一定会访问n个单链表
所有的单链表，表结点数相加就是e，即，图当中的边数
最后，就是n+e
空间复杂度，因为是递归算法
假设你的图比较极端
是这样一种情况
这时候，递归的深度是最深的
它所使用到的递归工作栈
容量就是n
我们也可以采用非递归的形式，来实现这个算法
如何将这个算法，改成非递归的形式呢
我们前面讲栈和递归的关系的时候，曾经提到过
虽然递归程序
在代码中没有用到栈
但是在执行过程当中，会有一个递归的(工作)栈
我们完全可以自己写代码，来模拟递归工作栈它的执行流程
从而把这个递归程序，改成非递归的程序
引入一个栈就可以了
我们访问每个顶点的时候
都把这个顶点入到栈里面去
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
