介绍
图的遍历是和树的遍历类似，从图中 某一顶点出发访遍图中其余顶点，且使 每一个顶点仅被访问一次， 这一过程就叫做图的遍历。
对于图的遍历来，通常有两种遍历：
- 深度优先遍历
- 广度优先遍历
深度优先遍历（垂直优先）
深度优先遍历(Depth First Search)，也有称为深度优先搜索，简称为DFS
步骤：
- 首先访问顶点
V（图没有根结点，可任意选一个顶点） - 依次从
V出发搜索V的任意优先一个邻接点W - 若
W未访问过，则从该点优先出发继续深度优先遍历；它类似于树的前序遍历。
例子：
遍历步骤：
V1 -> V2 -> V4 -> V8 -> V5- 之后走不通，然后 回溯 到
V1 v3 -> V6 -> V7
广度优先遍历（水平优先）
步骤：
- 首先访问顶点
V（图没有根结点，可任意选一个顶点） - 然后访问与顶点V邻接的 全部未访问 顶点
W、X、Y... - 然后再依次访问
W、X、Y...邻接的未访问的顶点。
例子：
遍历步骤：
- 从
v1出发，遍历V2、V3 - 从
v2出发，遍历V4、V5 - 从
v3出发，遍历V6、V7 - 从
v4出发，遍历V8
结合队列： 从上面步骤可知，从 V1 出发，遍历 V2、V3，将 V2、V3 放入到队列中，然后遍历该队列，先进先出，取出 V2 ，从 V2 出发
时间复杂度
遍历过程的时间复杂度只与 存储结构 有关系，与 深度优先遍历、广度优先遍历无关
邻接矩阵存储
如上图，矩阵中每个点都要遍历，图有 n 个顶点，矩阵的大小是 n * n，时间复杂度为 O(n²)
邻接表存储
有向图
如下图：邻接链表中元素的数量 = 图顶点数量 + 边的数量
时间复杂度为 O(n+e)
解释： e：图中边的数量
无向图
时间复杂度为 O(n+2e)
解释：
e：图中边的数量- 无向图每条边有两个方向，所以
2e
题
以下关于图的遍历的叙述中，正确的是（）
A、图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程
B、图的深度优先遍历方法不适用于无向图
C、使用队列对图进行广度优先遍历
D、图中有回路时则无法进行遍历
分析
选项A：错误，没有给定源点，图没有根结点，可从任意结点出发
选项B：错误，深度优先遍历方法，与图的类型无关
选项C：对
选项D：错，可以遍历
题
某有向图如下所示，从顶点v1出发对其进行深度优先遍历，可能得到的遍历序列是（）；从顶点v1出发对其进行广度优先遍历，可能得到的遍历序列是（）
① V1 V2 V3 V4 V5
② V1 V3 V4 V5 V2
③ V1 V3 V2 V4 V5
④ V1 V2 V4 V5 V3
A、①②③
B、①③④
C、①②④
D、②③④
A、①②
B、①③
C、②③
D、③④
问题1-分析
是 深度优先遍历
①不对，V1 -> V2 之后还可以垂直遍历，而不应该是 V3
技巧：所有包含 ① 的选项都排除
②对，V1 -> V3 -> V4 -> V5，走不通，回溯到 V3，访问 V2
③对，V1 -> V3 -> V2 -> V4 -> V5
④对，V1 -> V2 -> V4 -> V5，走不通，回溯到 V1，访问 V3
问题1-答案
D
问题2-分析
是广度优先遍历
①对
②不对，V3 之后应该是 V2
③对
④不对，V2 之后应该是 V3
问题2-答案
B