1
一,深度优先搜索
二,广度优先搜索
8.4 图的遍历
遍历定义,从已给的连通图中某一顶点出发，沿着一些边，访
遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做
图的遍历,它是 图的 基本运算 。
遍历实质,找每个顶点的邻接点的过程。
图的特点,图中可能存在 回路,且图的任一顶点都可能与其它
顶点相通，在访问完某个顶点之后可能会沿着某些边又回
到了曾经访问过的顶点 。
解决思路,可设置一个 辅助数组 visited [n ]，用来标记每个被
访问过的顶点。它的初始状态为 0，在图的遍历过程中，
一旦某一个顶点 i被访问，就立即改 visited [i]为 1，防止
它被多次访问。
图常用的遍历：
怎样避免重复访问？
2
一、深度优先搜索 ( DFS )
基本思想,—— 仿树的先序遍历过程 。
Depth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
DFS 结果例 1：
→ → → →
→ → →
v2 v4 v8
v5 v3 v6 v7
例 2：
v2 → v1 → v3 → v5 →
DFS 结果
v4 → v6
起点
起点
应退回到 V8，因为 V2已有标记
3
深度优先搜索（遍历）步骤：
详细归纳：
?在访问图中某一起始顶点 v后，由 v 出发，访问 它的任一邻接
顶点 w1；
?再从 w1 出发，访问 与 w1邻接 但还 未被访问 过的顶点 w2；
?然后再从 w2 出发，进行类似的访问,…
?如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u
为止。
?接着，退回一步,退到前一次刚访问过的顶点,看是否还有
其它未被访问的邻接顶点。
如果有,则访问此顶点，之后再从此顶点出发，进行与前述
类似的访问；
如果没有,就 再退回一步 进行搜索。重复上述过程，直到连
通图中所有顶点都被访问过为止。
简单归纳：
? 访问起始点 v;
? 若 v的第 1个邻接点没访问过，深度遍历此邻接点；
? 若当前邻接点已访问过，再找 v的第 2个邻接点重新遍历。
4
二、广度优先搜索 ( BFS )
基本思想,—— 仿树的层次遍历过程 。
Breadth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
BFS 结果例 1：
→ →
→
→v2 v3
→v4 v5 →v6 v7→ v8
例 2：
v3 →
BFS 结果
v4 → v5 →
起点
起点
v2 → v1 → v6 →
v9 → v8 → v7
5
广度优先搜索（遍历）步骤：
简单归纳：
? 在访问了起始点 v之后，依次访问 v的邻接点；
? 然后再依次 （顺序） 访问这些点 （下一层） 中未被
访问过的邻接点；
? 直到所有顶点都被访问过为止。
广度优先搜索是一种分层的搜索过程，每向前走一
步可能访问一批顶点，不像深度优先搜索那样有回
退的情况。
因此，广度优先搜索不是一个递归的过程，其算法
也不是递归的。
6
8.5 最小生成树
1、生成树,是一个极小连通子图，它含有图中全部顶点，但
只有 n-1条边。
2、最小生成树,如果无向连通图是一个带权图，那么它的所
有生成树中必有一棵边的权值总和为最小的生成树，
称这棵生成树为 最小代价生成树,简称 最小生成树。
一、最小生成树的基本概念
7
3.求最小生成树
首先明确：
? 使用不同的遍历图的方法，可以得到不同的生成树；从
不同的顶点出发，也可能得到不同的生成树。
? 按照生成树的定义,n 个顶点的 连通网络 的生成树肯定
有 n 个顶点 和仅仅 n-1 条边 。
即有权图
构造最小生成树的准则
? 必须只使用该网络中的 边 来构造最小生成树；
? 必须使用且仅使用 n-1条边 来联结网络中的 n个顶点；
? 不能使用产生回路的边。
目标,在网络的多个生成树中，寻找一个 各边权值之和
最小 的生成树。
8
欲在 n个城市间建立通信网，则 n个城市应铺 n-1条线路；但因
为每条线路都会有对应的经济成本，而 n个城市可能有
n(n-1)/2 条线路，那么,如何选择 n–1条线路使总费用最少？
4、典型用途：
先建立数学模型：
顶点 ———表示城市，有 n个；
边 ————表示线路，有 n–1条；
边的权值 —表示线路的经济代价；
连通网 ——表示 n个城市间的通信网。
显然此连通网
是一棵 生成树！
问题抽象,n个顶点的生成树很多，需要从中选一棵 代价最
小 的生成树，即该树 各边的代价之和 最小。此树便称为最小
生成树 MST。
9
讨论：如何求得最小生成树？
最小生成树 （ MST） 的 性质如下：
若 U集是 V的一个非空子集，若 (u0,v0)是一条 最小权值的
边,其中 u0?U,v0?V-U；则,(u0,v0)必在最小生成树上 。
设想一下,先把权值最小的边归入生
成树内，逐个递增，舍去回路边，则
得到的很可能就是最小生成树！
求 MST有多种算法，但最常用的是以下两种：
? Kruskal（ 克鲁斯卡尔 ）算法
? Prim（ 普里姆 ）算法
Kruskal算法特点,将边归并,适于求 稀疏网 的最小生成树。
Prime算法特点, 将顶点归并,与边数无关，适于 稠密网 。
对边操作
对顶点操作
10
二、普里姆算法
1、普里姆（ Prim)算法思想
令集合 U的初值为 U={u0}，集合 T={}。从所有结点 u∈U 和
结点 v∈ V\U的带权边中选出具有最小权值的边 (u,v)，将结
点 v加入集合 U中，将边 (u,v)加入集合 T中。如此不断重复，
当 U=V时，最小生成树便构造完毕。
2、普利姆（ Prim）算法 示例,归并顶点
1
2 43
5 6
6 1
6
5
5 5
63 4 2
最小代价生成树
1
2 43
5 6
1
5
3 4 2
Prim算法 是归并顶点，适用于稠密网。
11
A C
B G
E F
D
50
60
45
52
42
30
65
50
40
70
A C
B G
E F
D
A C
B G
E F
D
50
A C
B G
E F
D
50
40
A C
B G
E F
D
50
50
40
A C
B G
E F
D
50
3050
40
A C
B G
E F
D
50
42
3050
40
A C
B G
E F
D
50 45
42
3050
40
(a) (b) (c)
(d) (e) (f)
(g) (h)
例：利用普里姆算法构造最小生成树的过程
12
三、克鲁斯卡尔（ Kruska)算法
1,克鲁斯卡尔算法思想
设无向连通带权图 G=(V,E)，其中 V为 结点的集合, E为 边的集合 。设带
权图 G的最小生成树 T由结点集合和边的集合构成，其初值为 T=(V,{})，既
初始时最小生成树 T只由带权图 G中结点集合组成，各结点之间没有一条边。
这样，最小生成树 T中的各个结点各自构成一个连通分量。然后，按照边
的权值递增的顺序考察带权图 G中边集合 E的各条边，若被考察的边的两个
结点属于 T的两个不同的连通分量，则将此边加入到最小生成树 T中，同时，
把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于 T的
同一个连通分量，则将此边舍去。如此下去，当 T中的连通分量个数为 1时，
T中的该连通分量即为带权图 G的一棵最小生成树。
2,克鲁斯卡尔算法 示例,
1
2 43
5 6
6 1
6
5
5 5
63 4 2
最小代价生成树
1
2 43
5 6
1
5
3 4 2
5
5
Kruskal算法 是归并边，适用于稀疏图
13
A C
B G
E F
D
30
A C
B G
E F
D
30
40
A C
B G
E F
D
42
30
40
A C
B G
E F
D
45
42
30
40
A C
B G
E F
D
50 45
42
30
40
A C
B G
E F
D
50 45
42
3050
40
(a) (b) (c)
(d) (e) (f)
例：利用克鲁斯卡尔算法构造最小生成树的过程
14
8.6 最短路径
典型用途,交通问题。如：城市 A到城市 B有多条线路，但每条
线路的交通费（或所需时间）不同，那么,如何选择一条线路，
使总费用（或总时间）最少？
问题抽象,在 带权有向图 中 A点（源点）到达 B点（终点）的多
条路径中，寻找一条 各边权值之和最小 的路径，即最短路径。
（注：最短路径与最小生成树不同，路径上不一定包含 n个顶点）
两种常见的最短路径问题：
一,单源最短路径 — 用 Dijkstra（迪杰斯特拉） 算法
二、所有顶点间的最短路径 — 用 Floyd（弗洛伊德） 算法
一顶点到其
余各顶点任意两顶
点之间
15
一、最短路径的基本概念
1、图的最短路径 和 最短路径长度
图中从一个结点到另一个结点可能存在多条路径，路径
长度最短的那条路径称作 最短路径 。其长度称作 最短路径长
度 。
2,带权图 的最短路径 和 最短路径长度
带权图中从一个结点到另一个结点可能存在多条路径，
带权路径长度最短的那条路径称作 最短路径 。其带权路径长
度称作 最短路径长度 。
二,从一个结点（某个源点）到其余各顶点的最短路径（单源
最短路径问题）
16
1、狄克斯特拉 (Dijkstra) 算法思想
设置两个结点的 集合 S和 T，集合 S中存放 已找到 最短路
径的 结点,集合 T中存放当前 还未找到 最短路径的 结点 。初
始状态时，集合 S中只包含源点，设为 v0，然后不断从集合 T
中选择到源点 v0路径长度最短的结点 u加入到集合 S中,集合
S中每加入一个新的结点 u都要修改从源点 v0到集合 T中剩余
结点的当前最短路径长度值，集合 T中各结点的新的当前最
短路径长度值，为原来的最短路径长度值与从源点过结点 u
到达该结点的路径长度中的较小者。此过程不断重复，直到
集合 T中的结点全部加入到集合 S中为止。E
F
D
B
C
A
8
2
5
3018
10
7
15
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
????
?????
???
???
???
01810
04
0
7015
802
3050
(a) (b)
4例：利用狄克斯特拉算法求如下所示图中从顶点 A到其余各顶点的最短路径的过程。
17
E
F
D
B
C
A
5
18
10
7
15
E
F
D
B
C
A
5
30
(a)
E
F
D
B
C
A
5
30
7
15
E
F
D
B
C
A
5
30
18
10
7
15
E
F
D
B
C
A
8
5
18
10
7
15
E
F
D
B
C
A
8
5
10
7
15
(b) (c)
(d) (e) (f)
18
1、采用狄克斯特拉算法实现
算法思想：每次以不同的结点作为源点，调用狄克斯特拉
算法求出从该源点到其余结点的最短路径。需重复调用 n次狄
克斯特拉算法。
2、采用弗洛伊德算法，其算法思想如下：
二,每一对顶点之间的最短路径
可以用如下递推公式描述：
A0[i][j]=cost[i][j]
Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤ k≤ n-1)
其中,cost[i][j]中存放着序号为 i的结点到序号为 j的结点之
间的权值 ； Ak[i][j](0≤ k≤ n-1) 表示从结点 vi到结点 vj的路径
上所经过的结点序号不大于 k的最短路径长度。
19
图
存储结构
遍 历
邻接矩阵
邻 接 表
十字链表
邻接多重表
深度优先搜索
广度优先搜索
无向图的应用
应用
图的连通分量
图的生成树 最小生成树 Prim算法
Kruskal算法
最短路径 Dijkstra算法
Floyd算法
（利用 DFS）
第 8章 小结
一,深度优先搜索
二,广度优先搜索
8.4 图的遍历
遍历定义,从已给的连通图中某一顶点出发，沿着一些边，访
遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做
图的遍历,它是 图的 基本运算 。
遍历实质,找每个顶点的邻接点的过程。
图的特点,图中可能存在 回路,且图的任一顶点都可能与其它
顶点相通，在访问完某个顶点之后可能会沿着某些边又回
到了曾经访问过的顶点 。
解决思路,可设置一个 辅助数组 visited [n ]，用来标记每个被
访问过的顶点。它的初始状态为 0，在图的遍历过程中，
一旦某一个顶点 i被访问，就立即改 visited [i]为 1，防止
它被多次访问。
图常用的遍历：
怎样避免重复访问？
2
一、深度优先搜索 ( DFS )
基本思想,—— 仿树的先序遍历过程 。
Depth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
DFS 结果例 1：
→ → → →
→ → →
v2 v4 v8
v5 v3 v6 v7
例 2：
v2 → v1 → v3 → v5 →
DFS 结果
v4 → v6
起点
起点
应退回到 V8，因为 V2已有标记
3
深度优先搜索（遍历）步骤：
详细归纳：
?在访问图中某一起始顶点 v后，由 v 出发，访问 它的任一邻接
顶点 w1；
?再从 w1 出发，访问 与 w1邻接 但还 未被访问 过的顶点 w2；
?然后再从 w2 出发，进行类似的访问,…
?如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u
为止。
?接着，退回一步,退到前一次刚访问过的顶点,看是否还有
其它未被访问的邻接顶点。
如果有,则访问此顶点，之后再从此顶点出发，进行与前述
类似的访问；
如果没有,就 再退回一步 进行搜索。重复上述过程，直到连
通图中所有顶点都被访问过为止。
简单归纳：
? 访问起始点 v;
? 若 v的第 1个邻接点没访问过，深度遍历此邻接点；
? 若当前邻接点已访问过，再找 v的第 2个邻接点重新遍历。
4
二、广度优先搜索 ( BFS )
基本思想,—— 仿树的层次遍历过程 。
Breadth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
BFS 结果例 1：
→ →
→
→v2 v3
→v4 v5 →v6 v7→ v8
例 2：
v3 →
BFS 结果
v4 → v5 →
起点
起点
v2 → v1 → v6 →
v9 → v8 → v7
5
广度优先搜索（遍历）步骤：
简单归纳：
? 在访问了起始点 v之后，依次访问 v的邻接点；
? 然后再依次 （顺序） 访问这些点 （下一层） 中未被
访问过的邻接点；
? 直到所有顶点都被访问过为止。
广度优先搜索是一种分层的搜索过程，每向前走一
步可能访问一批顶点，不像深度优先搜索那样有回
退的情况。
因此，广度优先搜索不是一个递归的过程，其算法
也不是递归的。
6
8.5 最小生成树
1、生成树,是一个极小连通子图，它含有图中全部顶点，但
只有 n-1条边。
2、最小生成树,如果无向连通图是一个带权图，那么它的所
有生成树中必有一棵边的权值总和为最小的生成树，
称这棵生成树为 最小代价生成树,简称 最小生成树。
一、最小生成树的基本概念
7
3.求最小生成树
首先明确：
? 使用不同的遍历图的方法，可以得到不同的生成树；从
不同的顶点出发，也可能得到不同的生成树。
? 按照生成树的定义,n 个顶点的 连通网络 的生成树肯定
有 n 个顶点 和仅仅 n-1 条边 。
即有权图
构造最小生成树的准则
? 必须只使用该网络中的 边 来构造最小生成树；
? 必须使用且仅使用 n-1条边 来联结网络中的 n个顶点；
? 不能使用产生回路的边。
目标,在网络的多个生成树中，寻找一个 各边权值之和
最小 的生成树。
8
欲在 n个城市间建立通信网，则 n个城市应铺 n-1条线路；但因
为每条线路都会有对应的经济成本，而 n个城市可能有
n(n-1)/2 条线路，那么,如何选择 n–1条线路使总费用最少？
4、典型用途：
先建立数学模型：
顶点 ———表示城市，有 n个；
边 ————表示线路，有 n–1条；
边的权值 —表示线路的经济代价；
连通网 ——表示 n个城市间的通信网。
显然此连通网
是一棵 生成树！
问题抽象,n个顶点的生成树很多，需要从中选一棵 代价最
小 的生成树，即该树 各边的代价之和 最小。此树便称为最小
生成树 MST。
9
讨论：如何求得最小生成树？
最小生成树 （ MST） 的 性质如下：
若 U集是 V的一个非空子集，若 (u0,v0)是一条 最小权值的
边,其中 u0?U,v0?V-U；则,(u0,v0)必在最小生成树上 。
设想一下,先把权值最小的边归入生
成树内，逐个递增，舍去回路边，则
得到的很可能就是最小生成树！
求 MST有多种算法，但最常用的是以下两种：
? Kruskal（ 克鲁斯卡尔 ）算法
? Prim（ 普里姆 ）算法
Kruskal算法特点,将边归并,适于求 稀疏网 的最小生成树。
Prime算法特点, 将顶点归并,与边数无关，适于 稠密网 。
对边操作
对顶点操作
10
二、普里姆算法
1、普里姆（ Prim)算法思想
令集合 U的初值为 U={u0}，集合 T={}。从所有结点 u∈U 和
结点 v∈ V\U的带权边中选出具有最小权值的边 (u,v)，将结
点 v加入集合 U中，将边 (u,v)加入集合 T中。如此不断重复，
当 U=V时，最小生成树便构造完毕。
2、普利姆（ Prim）算法 示例,归并顶点
1
2 43
5 6
6 1
6
5
5 5
63 4 2
最小代价生成树
1
2 43
5 6
1
5
3 4 2
Prim算法 是归并顶点，适用于稠密网。
11
A C
B G
E F
D
50
60
45
52
42
30
65
50
40
70
A C
B G
E F
D
A C
B G
E F
D
50
A C
B G
E F
D
50
40
A C
B G
E F
D
50
50
40
A C
B G
E F
D
50
3050
40
A C
B G
E F
D
50
42
3050
40
A C
B G
E F
D
50 45
42
3050
40
(a) (b) (c)
(d) (e) (f)
(g) (h)
例：利用普里姆算法构造最小生成树的过程
12
三、克鲁斯卡尔（ Kruska)算法
1,克鲁斯卡尔算法思想
设无向连通带权图 G=(V,E)，其中 V为 结点的集合, E为 边的集合 。设带
权图 G的最小生成树 T由结点集合和边的集合构成，其初值为 T=(V,{})，既
初始时最小生成树 T只由带权图 G中结点集合组成，各结点之间没有一条边。
这样，最小生成树 T中的各个结点各自构成一个连通分量。然后，按照边
的权值递增的顺序考察带权图 G中边集合 E的各条边，若被考察的边的两个
结点属于 T的两个不同的连通分量，则将此边加入到最小生成树 T中，同时，
把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于 T的
同一个连通分量，则将此边舍去。如此下去，当 T中的连通分量个数为 1时，
T中的该连通分量即为带权图 G的一棵最小生成树。
2,克鲁斯卡尔算法 示例,
1
2 43
5 6
6 1
6
5
5 5
63 4 2
最小代价生成树
1
2 43
5 6
1
5
3 4 2
5
5
Kruskal算法 是归并边，适用于稀疏图
13
A C
B G
E F
D
30
A C
B G
E F
D
30
40
A C
B G
E F
D
42
30
40
A C
B G
E F
D
45
42
30
40
A C
B G
E F
D
50 45
42
30
40
A C
B G
E F
D
50 45
42
3050
40
(a) (b) (c)
(d) (e) (f)
例：利用克鲁斯卡尔算法构造最小生成树的过程
14
8.6 最短路径
典型用途,交通问题。如：城市 A到城市 B有多条线路，但每条
线路的交通费（或所需时间）不同，那么,如何选择一条线路，
使总费用（或总时间）最少？
问题抽象,在 带权有向图 中 A点（源点）到达 B点（终点）的多
条路径中，寻找一条 各边权值之和最小 的路径，即最短路径。
（注：最短路径与最小生成树不同，路径上不一定包含 n个顶点）
两种常见的最短路径问题：
一,单源最短路径 — 用 Dijkstra（迪杰斯特拉） 算法
二、所有顶点间的最短路径 — 用 Floyd（弗洛伊德） 算法
一顶点到其
余各顶点任意两顶
点之间
15
一、最短路径的基本概念
1、图的最短路径 和 最短路径长度
图中从一个结点到另一个结点可能存在多条路径，路径
长度最短的那条路径称作 最短路径 。其长度称作 最短路径长
度 。
2,带权图 的最短路径 和 最短路径长度
带权图中从一个结点到另一个结点可能存在多条路径，
带权路径长度最短的那条路径称作 最短路径 。其带权路径长
度称作 最短路径长度 。
二,从一个结点（某个源点）到其余各顶点的最短路径（单源
最短路径问题）
16
1、狄克斯特拉 (Dijkstra) 算法思想
设置两个结点的 集合 S和 T，集合 S中存放 已找到 最短路
径的 结点,集合 T中存放当前 还未找到 最短路径的 结点 。初
始状态时，集合 S中只包含源点，设为 v0，然后不断从集合 T
中选择到源点 v0路径长度最短的结点 u加入到集合 S中,集合
S中每加入一个新的结点 u都要修改从源点 v0到集合 T中剩余
结点的当前最短路径长度值，集合 T中各结点的新的当前最
短路径长度值，为原来的最短路径长度值与从源点过结点 u
到达该结点的路径长度中的较小者。此过程不断重复，直到
集合 T中的结点全部加入到集合 S中为止。E
F
D
B
C
A
8
2
5
3018
10
7
15
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
????
?????
???
???
???
01810
04
0
7015
802
3050
(a) (b)
4例：利用狄克斯特拉算法求如下所示图中从顶点 A到其余各顶点的最短路径的过程。
17
E
F
D
B
C
A
5
18
10
7
15
E
F
D
B
C
A
5
30
(a)
E
F
D
B
C
A
5
30
7
15
E
F
D
B
C
A
5
30
18
10
7
15
E
F
D
B
C
A
8
5
18
10
7
15
E
F
D
B
C
A
8
5
10
7
15
(b) (c)
(d) (e) (f)
18
1、采用狄克斯特拉算法实现
算法思想：每次以不同的结点作为源点，调用狄克斯特拉
算法求出从该源点到其余结点的最短路径。需重复调用 n次狄
克斯特拉算法。
2、采用弗洛伊德算法，其算法思想如下：
二,每一对顶点之间的最短路径
可以用如下递推公式描述：
A0[i][j]=cost[i][j]
Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤ k≤ n-1)
其中,cost[i][j]中存放着序号为 i的结点到序号为 j的结点之
间的权值 ； Ak[i][j](0≤ k≤ n-1) 表示从结点 vi到结点 vj的路径
上所经过的结点序号不大于 k的最短路径长度。
19
图
存储结构
遍 历
邻接矩阵
邻 接 表
十字链表
邻接多重表
深度优先搜索
广度优先搜索
无向图的应用
应用
图的连通分量
图的生成树 最小生成树 Prim算法
Kruskal算法
最短路径 Dijkstra算法
Floyd算法
（利用 DFS）
第 8章 小结
