C C A B A G F
E D B D C
F
G
E
visit(D)
B
D
(D, B) (D, C) visit(B)
C
(B, C) (B, D) visit(C) (C, A) (C, B) (C, D) visit(A) (A, C) (A, E)
输出：A C B D
未遍历 已标记
当前访问点
堆栈
无向图的深度优先搜索
visit(E) (E, A) visit(A) (A, C) (A, E)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D E
未遍历 已标记 visit(A) (A, C) (A, E)
E D B D C
F
G
E
B
D
C
输出：
未遍历 已标记
当前访问点
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A
未遍历 已标记 visit(A) (A, C) (A, E)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
void DFS(Graph G, int v) { visited[v]=1; Visit(v);
时间复杂度 (1) 采用邻接矩阵：O(n2) (2) 采用邻接表：O(n+e)
for (w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w); }
B
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D E F G
未遍历 已标记 visit(F) (F, G)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D E F G
第七章 图
Seven Bridges of Kö nigsberg(柯尼斯堡)
第七章 图
7.1 图的定义和基本术语
7.2 图的存储 7.3 图的遍历
7.4 图的连通性问题
7.5 有向无环图及其应用 7.6 最短路径
第七章 图
7.1 图的定义和基本术语
7.2 图的存储 7.3 图的遍历
7.4 图的连通性问题
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C
未遍历 已标记
visit(C) (C, A) (C, B) (C, D) visit(A) (A, C) (A, E)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D E F G
未遍历 已标记
visit(G) (G, F) visit(F) (F, G)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
F
G
E
visit(D)
B
D
(D, B) (D, C) visit(B)
C
(B, C) (B, D) visit(C) (C, A) (C, B) (C, D) visit(A) (A, C) (A, E)
输出：A C B D
未遍历 已标记
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
F
G
E
B
D
C
输出：A C B D E
未遍历 已标记
visit(E) (E, A) visit(A) (A, C) (A, E)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F

E D B D C
F
G
E
B
D
C
输出：A C B D E
未遍历 已标记
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C
未遍历 已标记
visit(C) (C, A) (C, B) (C, D) visit(A) (A, C) (A, E)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
未遍历 已标记
当前访问点
堆栈
深度优先搜索算法
void DFSTraverse(Graph G) { for (v=0; v<G.vexnum; v++) visited[v]=0; for (v=0; v<G.vexnum; v++) if (!visited[v]) DFS(G, v); }
深度优先搜索算法
深度优先搜索法的应用

求非连通图中的连通分量的个数； 寻找欧拉回路(Euler tour)的遍历路径。
作业
设在A、B、C、D四地之间架设有6座桥，要求从 某一地出发，经过每座桥恰巧一次，最后返回原地。
（1）此问题有解的条件是什么？
（2）设图中的顶点数为n，试用C语言描述与求解此 问题有关的数据结构并编写算法，找出满足要求的一 条回路。 A C D
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D E
未遍历 已标记
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D E F
未遍历 已标记 visit(F) (F, G)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D E F G
未遍历 已标记
visit(G) (G, F) visit(F) (F, G)
(2) 依次从v的未被访问的邻接点出发深度优先遍历， 直到与v有路径相通的所有顶点都被访问到；
(3) 若图中尚有顶点未被访问到，则选择其中一个顶 点作为新的起始点，重复(1)(2)步骤直到图中所有 顶点都访问完毕。
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
F
G
E
B
D
visit(B)
C
(B, C) (B, D)
visit(C)
输出：A C B
未遍历 已标记
(C, A) (C, B) (C, D) visit(A) (A, C) (A, E)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
什么是图的遍历？
从图中某一顶点出发访遍图中其余顶点，且使每 个顶点仅被访问一次，这一过程就叫做图的遍历。根 据遍历路径的不同，通常有两种遍历方法：

深度优先搜索
广度优先搜索
7.3.1 深度优先搜索


类似于树的先序遍历（使用堆栈） 遍历过程
(1) 假设初始状态图中顶点均未被访问，从顶点v出发 访问该顶点；
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
F
G
E
B
D
C
输出：A C B D
未遍历 已标记 visit(A) (A, C) (A, E)
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A
A: B: C: D: E: F: G:
C C A B A G F
E D B D C
未遍历 已标记
当前访问点
堆栈
无向图的深度优先搜索
邻接表：
A