第 7章 图
7.1 图的定义、术语和基本运算
7.2 图的存储结构
7.3 图的遍历与拓扑排序
7.4 最小生成树
7.5 最短路径
7.6 本章小结
7.1 图的定义、术语
和基本运算
7.1.1 图的定义及术语
图结构的形式化定义：
Graph=(V,R)，其中：
V={x | x?D,D是具有相同特性的数据元素的
集合 }；
R={Edge}，
Edge={<x,y> | P(x,y)?(x,y?V),谓词
P(x,y)定义了弧 <x,y>上的意义或信息 }。
1 2
3 4
5
1 2
3 4
5
( a ) 有向图 G
1
( b ) 无向图 G
2
图7, 1 图的示例
圆圈代表数据元素
圆圈之间的连线代
表数据元素之间的
关系
在图结构中，一个元素可以有多个
直接后继，也可以有多个直接前趋。
相关术语
? 顶点（ vertex）
?Edge是两个顶点之间的关系的集合,
<x,y>?Edge，则 <x,y>为 从 x到 y的
一条弧 ；
x为弧尾或始点 ； y为弧头或终点。
－－－－此时的图称为有向图 。
?若 Edge是对称的
用无序对 (x,y)表示 x和 y之间的一条
边 。－－－－ 此时的图称为无向图 。
?不考虑顶点到自身的边：
完全图,N个顶点，有 N(N-1)/2条边的无
向图；
有向完全图,N个顶点，有 N(N-1)条弧的
有向图；
?稀疏图 /稠密图
?网（ Network）,带边权的图
?子图,1 2
3 4
5
1 2
3 4
5
( a ) 有向图 G
1
的一些子图 ( b ) 无向图 G
2
的一些子图
图7, 2 图7, 1 中G
1
和G
2
的子图示例
1
3 4
5
?无向图中
两顶点 互 为 邻接点；
边和顶点 相关联； 顶点的度
?有向图中
邻接到 /邻接自
顶点的 入度 /出度
?图中的顶点与边 /弧之间有以下关系
? ??
?
?
n
1i
i2
1 vTDe
?路径
?路径的长度
?回路 /环
?简单路径
?简单回路 /简单环
?连通
?连通图
?连通分量
?强连通图 (有向图 )
?强连通分量
1 2
3 4
5
( a ) 图7, 1 ( a ) 中G
1
的3 个强联通分量
1 2
3 4
5
( b ) 图7, 1 ( a ) 中G
1
的生成森林示例
图7, 3 有向图的强联通分量与生成森林
?连通图的生成树
?有向图的生成森林
7.1.2 图的基本运算及其 ADT
? 图的基本运算
查找，插入和删除
顶点在图中的位置：
人为随意排列
?图的 ADT声明
ADT Graph
{ 数据对象为 D:
D是具有相同特性的数据元素的集合,称为
顶点集 。
数据间的关系 R:
R={Edge},
Edge={<x,y> | P(x,y)?(x,y?V),
谓词 P(x,y)定义了弧 <x,y>上的意义或信息 }
几种基本操作,
graphCreate(&graph)
graphDestroy (&graph)
graphClear(& graph)
创建空的图对
象 graph
销毁一个已有的图
graph
将图 graph清空
graphEmpty(graph)
graphCount(graph)
graphInsertVertex(&graph,
dataIn)
判图 graph是否
为空
求图 graph中顶
点个数
在图 graph中插入新顶
点,新顶点数据域的值是
dataIn
graphDeleteVertex(&graph,
dltKey)
graphInsertArc(&graph,
fromKey,toKey)
在图 graph中插入新弧,
弧头节点和弧尾节点关
键字是 fromKey和
toKey
在图 graph中删除顶点,
待删顶点数据域的关键
字是 dltKey
graphDeleteArc(&graph,
fromKey,toKey)
graphTraverse(graph,visit)
遍历图 graph各顶点,
并用 visit代表的操作
去处理各个顶点中的数
据
在图 graph中删除弧,
弧头节点和弧尾节点关
键字是 fromKey和
toKey
graphRetrieveVertex(graph,
key,& DataOut)
}
在图 graph中寻找关键
字为 key的顶点,并将其
信息放入 DataOut输出
参数中
7.2 图的存储结构
图的常用存储结构
?数组表示法－－连续存储方式
?邻接表
?邻接多重表 链式存储方式
?十字链表
7.2.1 数组表示法
设 G =(V,{E})是有 N(N≥ 1)个顶点
的图，则 G的邻接矩阵是具有如下性质的
N阶方阵：
1 若 <vi,vj>?E或 (vi,vj)?E
A[i,j]=
0 否则
对于无向图, 顶点 vi的度是邻接矩阵中第
i行 （ 或第 i列 ） 的元素之和 。
对于有向图，第 i行的元素之和为顶点 vi
的出度 OD(vi)，第 j列的元素之和为顶点 vj的
入度 ID(vj)。
网的邻接矩阵可定义为：
wij 若 <vi,vj>?E或 (vi,vj)?E
A[i,j]=
∞ 反之
00100
00010
10001
01001
00110
01000
00111
00000
10001
00100
2 4
3 5
6
1
10
20
30
40
50
60
70
80
90
?????
?????
?????
????
???
?????
50
90
10
4020
706030
80
( a ) 图7, 1 ( a ) 和( b ) 中G
1
和G
2
的邻接矩阵 ( b ) 网及其 邻接矩阵的示例
图7, 4 图与网对应的邻接矩阵
描述图时，我们同时使用两个数组,
一维数组中存储的是各个顶点的信息；
二维数组（邻接矩阵）中存储的是边
或弧的信息。
7.2.2 邻接表
infomation destination pNextArc
data pNextVertex pArc
1
2
3 ∧
4
5 ∧
1
2
3 ∧
4
5
3 ∧
1 5 ∧
1 2
4 ∧
2 ∧
3 ∧
0 4 ∧
0 1
3 ∧
2 ∧
1
2
3
4
5
1
3 ∧
4 ∧
1 ∧
1
2
3
4
0
1
2
3
4
0 3 ∧
0 3 ∧
destination pNextArc
data pArc
( a ) 网中的弧节点( 带信息域) ( b ) 图中的弧节点( 不带信息域)
( c ) 头节点( 构成链表) ( d ) 头节点( 构成数组)
( e ) 图7, 1 ( a ) 中G
1
的邻接表
( 头节点构成链表)
( f ) 图7, 1 ( a ) 中G
1
的邻接表
( 头节点构成数组)
( g ) 图7, 1 ( a ) 中G
1
的逆邻接
表( 头节点构成数组)
图7, 5 图结构的邻接表与逆邻接表
数组
下标
数组
下标
在无向图的邻接表中，顶点 vi的度恰
为第 i个链表中的节点数；而在有向图中，
第 i个链表中的节点数只是顶点 vi的出度；
为求入度，必须对整个邻接表扫描一遍。在
所有链表中其邻接点域的值为 i的节点的个
数是顶点 vi的入度。
有时，为了便于求每个顶点的入度，
尚需建立一个有向图的逆邻接表，即对每个
顶点 vi建立以 vi为弧头的链表。
7.2.3 邻接多重表
1
2
3
4
5
- 0
1
2
3
4
0
iVex iLink
数组
下标
1 ∧
- 1 3 ∧
- 2 0 ∧
- 4 ∧ 2 ∧
jVex jLinkmark
data firstEdge
info tailVex tLinkheadVex hLink
data firstIn
info
firstOut
firstOut
firstIn
2
3
∧
4
5
1
1
2
3
4
0
数组
下标
0 2 ∧
1 0 1 4 ∧ ∧
3 0 ∧ 3 1 ∧
4 3 ∧ ∧
3 2 ∧ ∧
( a ) 邻接多重表的边节点 ( d ) 十字链表的弧节点
( b ) 邻接多重表的头节点 ( e ) 十字链表的头节点
( c ) 图7, 1 ( b ) 中无向图G
2
的邻接多重表
( f ) 图7, 1 ( a ) 中有向图G
1
的十字链表
图7, 6 邻接多重表与十字链表的示例
data
邻接多重表
适宜作无向图的存储结构。
在无向图的邻接表表示法中，每条边
(vi,vj)是用两个表节点表示的。这给某些
图的操作带来不便。
7.2.4 十字链表
十字链表：
将有向图的邻接表和逆邻接表结合在
一起得到的一种链表。
图示参看 图 7.6
1
2
3
4
5
- 0
1
2
3
4
0
iVex iLink
数组
下标
1 ∧
- 1 3 ∧
- 2 0 ∧
- 4 ∧ 2 ∧
jVex jLinkmark
data firstEdge
info tailVex tLinkheadVex hLink
data firstIn
info
firstOut
firstOut
firstIn
2
3
∧
4
5
1
1
2
3
4
0
数组
下标
0 2 ∧
1 0 1 4 ∧ ∧
3 0 ∧ 3 1 ∧
4 3 ∧ ∧
3 2 ∧ ∧
( a ) 邻接多重表的边节点 ( d ) 十字链表的弧节点
( b ) 邻接多重表的头节点 ( e ) 十字链表的头节点
( c ) 图7, 1 ( b ) 中无向图G
2
的邻接多重表
( f ) 图7, 1 ( a ) 中有向图G
1
的十字链表
图7, 6 邻接多重表与十字链表的示例
data
在十字链表中既容易找到以 vi为
尾的弧，也容易找到以 vi为头的弧，因
而容易求得顶点的出度和入度（若需要，
可在建立十字链表的同时求出）。在某
些有向图的应用中，十字链表是很有用
的工具。
7.3 图的遍历与拓扑排序
? 7.3.1 图的遍历
遍历图的方法：
深度优先搜索
（ Depth First Search）
广度优先搜索
（ Breadth First Search）
1
2 3 4
5
1
2 3 4
5
1
2 3 4
5
( a ) 无向图G ( b ) 无向图G 的深度优先搜索过程 ( c ) 无向图G 的广度优先搜索过程
图7.7 图结构的两种遍历方式
深度优先搜索体现了优先向纵深发展
的趋势 。算法思路可考虑 回溯法 。
时间复杂度为 O(n+e)。
广度优先搜索 需要借助 队列,其时间
复杂度与 深度优先搜索相同。
7.3.2 拓扑排序
有向无环图,
Direct Acycline Graph，
简称 DAG图，无环的有向图。
有向无环图是描述一项工程或系
统其进行过程的有效工具。
拓扑排序（ Topological Sort）
由某个集合上的一个偏序得到该集合
上的一个全序的运算。
当图中顶点数量与弧的数目分别为 n
和 e时，时间复杂度为 O(n+e)。
拓扑排序本质上是图的遍历，其时
间复杂度为 O(n)，故整个算法时间复杂度
为 O(n+e)。
1 2 3
4
10
7
9 6
811 5
课程名称
高等数学
高级语言
数据结构
操作系统
计算机组成原理
数据库原理
编译原理
计算机网络
人工智能原理
软件工程
离散数学
课程编号
1
2
3
4
5
6
7
8
9
10
11
先行课
－
－
－
3,2
4,6
2
5
4,7
5,1
1,2,3
7,9
( a ) 计算机主干课程表
( b ) 课程关系图
图7, 8 课程表与课程关系图
学生的选课问题（拓扑排序问题）：
拓扑排序后的序列可有多种 。 下面就是
其中的两种拓扑序列 。
第一种是,1,2,3,6,4,10,5，
7,9,8,11；
第二种是,3,2,6,4,5,7,8,1，
10,9,11。
7.4 最小生成树
在连通网的生成树中选择这样一棵生成树，
使它在所有生成树中总的耗费最小，即为此连
通网的最小生成树。
最小生成树的 MST性质：假设 N
=(V,{E})是一个连通网,U是顶点集 V的一个
非空子集，若 (u,v)是一条具有最小权值
（代价）的边，其中 u?U,v?V-U，则必存
在一棵包含边 (u,v)的最小生成树。
最小生成树的两种算法：
?Kruskal算法
?Prim算法
基于 MST性质，
使用了贪心算
法的思想
Kruskal算法
按边权值的递增顺序，依次找出权
值最低的边来构建最小生成树，而且规
定每次新增的边，不能使已生成的部分
出现回路。对于 N个顶点的连通图来说，
当已找出 N-1条边时，过程结束。
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
图7, 9 K r u s k a l 算法选边的过程
(a) (b)
(c)
(d) (e) (f)
Prim算法
与 Kruskal算法 思路类似，区别在
于,每次加入的新边都会与已生成部分
相邻接，将顶点逐个连通而成最小生成
树 。
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
图7, 1 0 P r i m 算法选边的过程
(a) (b)
(c)
(d) (e) (f)
7.5 最短路径
带权图中求最短路径的问题，即求两
个顶点间长度最短的路径。
注意,这里路径长度指的是路径上的
边所带权的总和，而不是路径上边数的总
和。
7.5.1 单源最短路径问题与分支限界法
单源最短路径问题,
Dijkstra算法
Dijkstra算法解决 单源最短路径的基本
策略是：
先求出长度最小的一条最短路, 然后求出
长度第二小的最短路径, …,最后求出长度
最大的最短路径 。
应用 Dijkstra算法的求解过程示例
A
B
E
F
D
C
6
3
2
5
4
3 2
5
3
CB
A
6 3
C
B D E
B
A
6
3
5 6 7
C
B D E
D
B
A
6 3
5 6 7
10
C
B D E
E FD
B
A
6 3
5 6 7
10 8 9
C
B D E
E F FD
B
A
6
3
5 6 7
10 8 9 12
C
B D E
B
A
6
3
5 6 7
C
B D E
E F FD
B
A
6
3
5 6 7
10 8 9 12
(a) (b) (c) (d)
(e) (f) (g) (h)
图7, 1 1 单源最短路径的解空间树
从解空间树中我们得到源点 A到
网中其他顶点的最短路径的分析过程
中，使用了分支限界法 (Branch and
Bound)的思想。
分支限界法与回溯法的对比：
同,同为在问题的解空间树上搜索问
题解的方法。
异,
1,求解目标不同：回溯法的求解目标
是找出解空间树中满足约束条件的所有解，而
分支限界法的求解目标则是找出满足约束条件
的一个解，或是在满足约束条件的解中找出使
某一目标函数值达到极大或极小的解，即在某
种意义下的最优解。
2,对解空间树的搜索方式不同：
回溯法以深度优先的方式搜索解
空间树，而分支限界法则以广度优先或以
最小耗费（最大效益）优先的方式搜索解
空间树。
由于有双重循环，故对于含有 N个
顶点的有向网来说,Dijkstra算法总的
时间复杂度是 O(N2)。
7.5.2 多源最短路径问题与动态规划法
多源最短路径问题：
方法一：每次以一个顶点为源点，重
复执行 Dijkstra 算法 N次。
效率与 方法一 同阶，
但形式相对简单
方法二,Floyed算法
Floyed 算法从图的带权邻接矩阵 cost
出发，其基本思想是：
假设求从顶点 vi到 vj 的最短路径 。 如果从 vi到
vj有弧, 则从 vi到 vj存在一条长度为 cost[i,j]的
路径 。
该路径不一定是最短路径, 尚需进行 N次试探 。
首先考虑路径 (vi,v1,vj)是否存在 （ 即判断弧
(vi,v1)和 (v1,vj)是否存在 ） 。 如果存在, 则比较
其路径长度 。 取长度较短者为从 vi到 vj的中间顶点的
序号不大于 1的最短路径 。
假如在路径上再增加一个顶点 v2,即如果
(vi,…,v2)和 (v2,…,vj)分别是当前找到的中间顶
点的序号不大于 1 的最短路径, 那么,
(vi,…,v2,…,vj)就有可能是从 vi到 vj中间顶点的序
号不大于 2的最短路径 。 将它和已经得到的从 vi到 vj
中间顶点序号不大于 1的最短路径相比较, 从中选出
较小者做为中间顶点的序号不大于 2的最短路径 。
之后, 再增加一个顶点 v3,继续进行试探 。 依
此类推, …, 直至经过 N次比较, 最后求得的就是从
vi到 vj中间顶点的序号不大于 N的最短路径 。 因为有
向网中只有 N个顶点, 故该路径就是从 vi到 vj的最短
路径 。 按此方法, 可以同时求得各对顶点间的最短
路径 。
Floyed 算法中，新一步的结果总是
基于上一步的结果，所以每次运算都无需从
头做起，这正是动态规划 (Dynamic
Programming)算法的典型设计思想。
动态规划法与分治法 的对比：
同, 在解决问题时基于问题的划分：
将问题实例归纳为更小的、相似的子问题，
并通过求解子问题产生一个全局最优解。
异,
分治法中，各个子问题是独立的 (即不
包含公共的子问题 )，因此一旦递归地求出各
子问题的解后，便可自下而上地将子问题的解
合并成问题的解。要做许多不必要的重复工作。
动态规划法中，整个问题的最优解是由
各个子问题的最优解构成的。在求解过程中，
每个子解都是在前面的结果上得出的新的子解，
子解随着步骤的进行而逐步扩大，最后一步得
到完整的解。
7.6 本章小结
? 基本内容：
1,图的定义，有关术语；
2,图的四种存储结构；
3,图的两种遍历方法：深度优先遍
历和广度优先遍历；拓扑排序问题；
4,最小生成树；
5,图的最短路径问题；分支限界法
与动态规划法。
? 基本要求：
熟悉图的各种 存储结构 及其 构造算
法, 了解实际问题的求解效率与采用
何种存储结构和算法有密切联系 。
熟练掌握图的 两种搜索路径 的遍历：
遍历的 逻辑定义, 深度优先 搜索和 广
度优先 搜索的算法 。
在学习中应注意 图 的遍历算法与 树 的
遍历算法之间的 类似和差异 。 树的先根
遍历是一种深度优先搜索策略, 树的层
次遍历是一种广度优先搜索策略 。
理解实际 应用 中各种图的算法 。
学习并使用 动态规划 法与 分支限界 法
的思想 。
7.1 图的定义、术语和基本运算
7.2 图的存储结构
7.3 图的遍历与拓扑排序
7.4 最小生成树
7.5 最短路径
7.6 本章小结
7.1 图的定义、术语
和基本运算
7.1.1 图的定义及术语
图结构的形式化定义：
Graph=(V,R)，其中：
V={x | x?D,D是具有相同特性的数据元素的
集合 }；
R={Edge}，
Edge={<x,y> | P(x,y)?(x,y?V),谓词
P(x,y)定义了弧 <x,y>上的意义或信息 }。
1 2
3 4
5
1 2
3 4
5
( a ) 有向图 G
1
( b ) 无向图 G
2
图7, 1 图的示例
圆圈代表数据元素
圆圈之间的连线代
表数据元素之间的
关系
在图结构中，一个元素可以有多个
直接后继，也可以有多个直接前趋。
相关术语
? 顶点（ vertex）
?Edge是两个顶点之间的关系的集合,
<x,y>?Edge，则 <x,y>为 从 x到 y的
一条弧 ；
x为弧尾或始点 ； y为弧头或终点。
－－－－此时的图称为有向图 。
?若 Edge是对称的
用无序对 (x,y)表示 x和 y之间的一条
边 。－－－－ 此时的图称为无向图 。
?不考虑顶点到自身的边：
完全图,N个顶点，有 N(N-1)/2条边的无
向图；
有向完全图,N个顶点，有 N(N-1)条弧的
有向图；
?稀疏图 /稠密图
?网（ Network）,带边权的图
?子图,1 2
3 4
5
1 2
3 4
5
( a ) 有向图 G
1
的一些子图 ( b ) 无向图 G
2
的一些子图
图7, 2 图7, 1 中G
1
和G
2
的子图示例
1
3 4
5
?无向图中
两顶点 互 为 邻接点；
边和顶点 相关联； 顶点的度
?有向图中
邻接到 /邻接自
顶点的 入度 /出度
?图中的顶点与边 /弧之间有以下关系
? ??
?
?
n
1i
i2
1 vTDe
?路径
?路径的长度
?回路 /环
?简单路径
?简单回路 /简单环
?连通
?连通图
?连通分量
?强连通图 (有向图 )
?强连通分量
1 2
3 4
5
( a ) 图7, 1 ( a ) 中G
1
的3 个强联通分量
1 2
3 4
5
( b ) 图7, 1 ( a ) 中G
1
的生成森林示例
图7, 3 有向图的强联通分量与生成森林
?连通图的生成树
?有向图的生成森林
7.1.2 图的基本运算及其 ADT
? 图的基本运算
查找，插入和删除
顶点在图中的位置：
人为随意排列
?图的 ADT声明
ADT Graph
{ 数据对象为 D:
D是具有相同特性的数据元素的集合,称为
顶点集 。
数据间的关系 R:
R={Edge},
Edge={<x,y> | P(x,y)?(x,y?V),
谓词 P(x,y)定义了弧 <x,y>上的意义或信息 }
几种基本操作,
graphCreate(&graph)
graphDestroy (&graph)
graphClear(& graph)
创建空的图对
象 graph
销毁一个已有的图
graph
将图 graph清空
graphEmpty(graph)
graphCount(graph)
graphInsertVertex(&graph,
dataIn)
判图 graph是否
为空
求图 graph中顶
点个数
在图 graph中插入新顶
点,新顶点数据域的值是
dataIn
graphDeleteVertex(&graph,
dltKey)
graphInsertArc(&graph,
fromKey,toKey)
在图 graph中插入新弧,
弧头节点和弧尾节点关
键字是 fromKey和
toKey
在图 graph中删除顶点,
待删顶点数据域的关键
字是 dltKey
graphDeleteArc(&graph,
fromKey,toKey)
graphTraverse(graph,visit)
遍历图 graph各顶点,
并用 visit代表的操作
去处理各个顶点中的数
据
在图 graph中删除弧,
弧头节点和弧尾节点关
键字是 fromKey和
toKey
graphRetrieveVertex(graph,
key,& DataOut)
}
在图 graph中寻找关键
字为 key的顶点,并将其
信息放入 DataOut输出
参数中
7.2 图的存储结构
图的常用存储结构
?数组表示法－－连续存储方式
?邻接表
?邻接多重表 链式存储方式
?十字链表
7.2.1 数组表示法
设 G =(V,{E})是有 N(N≥ 1)个顶点
的图，则 G的邻接矩阵是具有如下性质的
N阶方阵：
1 若 <vi,vj>?E或 (vi,vj)?E
A[i,j]=
0 否则
对于无向图, 顶点 vi的度是邻接矩阵中第
i行 （ 或第 i列 ） 的元素之和 。
对于有向图，第 i行的元素之和为顶点 vi
的出度 OD(vi)，第 j列的元素之和为顶点 vj的
入度 ID(vj)。
网的邻接矩阵可定义为：
wij 若 <vi,vj>?E或 (vi,vj)?E
A[i,j]=
∞ 反之
00100
00010
10001
01001
00110
01000
00111
00000
10001
00100
2 4
3 5
6
1
10
20
30
40
50
60
70
80
90
?????
?????
?????
????
???
?????
50
90
10
4020
706030
80
( a ) 图7, 1 ( a ) 和( b ) 中G
1
和G
2
的邻接矩阵 ( b ) 网及其 邻接矩阵的示例
图7, 4 图与网对应的邻接矩阵
描述图时，我们同时使用两个数组,
一维数组中存储的是各个顶点的信息；
二维数组（邻接矩阵）中存储的是边
或弧的信息。
7.2.2 邻接表
infomation destination pNextArc
data pNextVertex pArc
1
2
3 ∧
4
5 ∧
1
2
3 ∧
4
5
3 ∧
1 5 ∧
1 2
4 ∧
2 ∧
3 ∧
0 4 ∧
0 1
3 ∧
2 ∧
1
2
3
4
5
1
3 ∧
4 ∧
1 ∧
1
2
3
4
0
1
2
3
4
0 3 ∧
0 3 ∧
destination pNextArc
data pArc
( a ) 网中的弧节点( 带信息域) ( b ) 图中的弧节点( 不带信息域)
( c ) 头节点( 构成链表) ( d ) 头节点( 构成数组)
( e ) 图7, 1 ( a ) 中G
1
的邻接表
( 头节点构成链表)
( f ) 图7, 1 ( a ) 中G
1
的邻接表
( 头节点构成数组)
( g ) 图7, 1 ( a ) 中G
1
的逆邻接
表( 头节点构成数组)
图7, 5 图结构的邻接表与逆邻接表
数组
下标
数组
下标
在无向图的邻接表中，顶点 vi的度恰
为第 i个链表中的节点数；而在有向图中，
第 i个链表中的节点数只是顶点 vi的出度；
为求入度，必须对整个邻接表扫描一遍。在
所有链表中其邻接点域的值为 i的节点的个
数是顶点 vi的入度。
有时，为了便于求每个顶点的入度，
尚需建立一个有向图的逆邻接表，即对每个
顶点 vi建立以 vi为弧头的链表。
7.2.3 邻接多重表
1
2
3
4
5
- 0
1
2
3
4
0
iVex iLink
数组
下标
1 ∧
- 1 3 ∧
- 2 0 ∧
- 4 ∧ 2 ∧
jVex jLinkmark
data firstEdge
info tailVex tLinkheadVex hLink
data firstIn
info
firstOut
firstOut
firstIn
2
3
∧
4
5
1
1
2
3
4
0
数组
下标
0 2 ∧
1 0 1 4 ∧ ∧
3 0 ∧ 3 1 ∧
4 3 ∧ ∧
3 2 ∧ ∧
( a ) 邻接多重表的边节点 ( d ) 十字链表的弧节点
( b ) 邻接多重表的头节点 ( e ) 十字链表的头节点
( c ) 图7, 1 ( b ) 中无向图G
2
的邻接多重表
( f ) 图7, 1 ( a ) 中有向图G
1
的十字链表
图7, 6 邻接多重表与十字链表的示例
data
邻接多重表
适宜作无向图的存储结构。
在无向图的邻接表表示法中，每条边
(vi,vj)是用两个表节点表示的。这给某些
图的操作带来不便。
7.2.4 十字链表
十字链表：
将有向图的邻接表和逆邻接表结合在
一起得到的一种链表。
图示参看 图 7.6
1
2
3
4
5
- 0
1
2
3
4
0
iVex iLink
数组
下标
1 ∧
- 1 3 ∧
- 2 0 ∧
- 4 ∧ 2 ∧
jVex jLinkmark
data firstEdge
info tailVex tLinkheadVex hLink
data firstIn
info
firstOut
firstOut
firstIn
2
3
∧
4
5
1
1
2
3
4
0
数组
下标
0 2 ∧
1 0 1 4 ∧ ∧
3 0 ∧ 3 1 ∧
4 3 ∧ ∧
3 2 ∧ ∧
( a ) 邻接多重表的边节点 ( d ) 十字链表的弧节点
( b ) 邻接多重表的头节点 ( e ) 十字链表的头节点
( c ) 图7, 1 ( b ) 中无向图G
2
的邻接多重表
( f ) 图7, 1 ( a ) 中有向图G
1
的十字链表
图7, 6 邻接多重表与十字链表的示例
data
在十字链表中既容易找到以 vi为
尾的弧，也容易找到以 vi为头的弧，因
而容易求得顶点的出度和入度（若需要，
可在建立十字链表的同时求出）。在某
些有向图的应用中，十字链表是很有用
的工具。
7.3 图的遍历与拓扑排序
? 7.3.1 图的遍历
遍历图的方法：
深度优先搜索
（ Depth First Search）
广度优先搜索
（ Breadth First Search）
1
2 3 4
5
1
2 3 4
5
1
2 3 4
5
( a ) 无向图G ( b ) 无向图G 的深度优先搜索过程 ( c ) 无向图G 的广度优先搜索过程
图7.7 图结构的两种遍历方式
深度优先搜索体现了优先向纵深发展
的趋势 。算法思路可考虑 回溯法 。
时间复杂度为 O(n+e)。
广度优先搜索 需要借助 队列,其时间
复杂度与 深度优先搜索相同。
7.3.2 拓扑排序
有向无环图,
Direct Acycline Graph，
简称 DAG图，无环的有向图。
有向无环图是描述一项工程或系
统其进行过程的有效工具。
拓扑排序（ Topological Sort）
由某个集合上的一个偏序得到该集合
上的一个全序的运算。
当图中顶点数量与弧的数目分别为 n
和 e时，时间复杂度为 O(n+e)。
拓扑排序本质上是图的遍历，其时
间复杂度为 O(n)，故整个算法时间复杂度
为 O(n+e)。
1 2 3
4
10
7
9 6
811 5
课程名称
高等数学
高级语言
数据结构
操作系统
计算机组成原理
数据库原理
编译原理
计算机网络
人工智能原理
软件工程
离散数学
课程编号
1
2
3
4
5
6
7
8
9
10
11
先行课
－
－
－
3,2
4,6
2
5
4,7
5,1
1,2,3
7,9
( a ) 计算机主干课程表
( b ) 课程关系图
图7, 8 课程表与课程关系图
学生的选课问题（拓扑排序问题）：
拓扑排序后的序列可有多种 。 下面就是
其中的两种拓扑序列 。
第一种是,1,2,3,6,4,10,5，
7,9,8,11；
第二种是,3,2,6,4,5,7,8,1，
10,9,11。
7.4 最小生成树
在连通网的生成树中选择这样一棵生成树，
使它在所有生成树中总的耗费最小，即为此连
通网的最小生成树。
最小生成树的 MST性质：假设 N
=(V,{E})是一个连通网,U是顶点集 V的一个
非空子集，若 (u,v)是一条具有最小权值
（代价）的边，其中 u?U,v?V-U，则必存
在一棵包含边 (u,v)的最小生成树。
最小生成树的两种算法：
?Kruskal算法
?Prim算法
基于 MST性质，
使用了贪心算
法的思想
Kruskal算法
按边权值的递增顺序，依次找出权
值最低的边来构建最小生成树，而且规
定每次新增的边，不能使已生成的部分
出现回路。对于 N个顶点的连通图来说，
当已找出 N-1条边时，过程结束。
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
图7, 9 K r u s k a l 算法选边的过程
(a) (b)
(c)
(d) (e) (f)
Prim算法
与 Kruskal算法 思路类似，区别在
于,每次加入的新边都会与已生成部分
相邻接，将顶点逐个连通而成最小生成
树 。
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
2
1
5 6
3
4
6 5
55
1
6
6
43 2
图7, 1 0 P r i m 算法选边的过程
(a) (b)
(c)
(d) (e) (f)
7.5 最短路径
带权图中求最短路径的问题，即求两
个顶点间长度最短的路径。
注意,这里路径长度指的是路径上的
边所带权的总和，而不是路径上边数的总
和。
7.5.1 单源最短路径问题与分支限界法
单源最短路径问题,
Dijkstra算法
Dijkstra算法解决 单源最短路径的基本
策略是：
先求出长度最小的一条最短路, 然后求出
长度第二小的最短路径, …,最后求出长度
最大的最短路径 。
应用 Dijkstra算法的求解过程示例
A
B
E
F
D
C
6
3
2
5
4
3 2
5
3
CB
A
6 3
C
B D E
B
A
6
3
5 6 7
C
B D E
D
B
A
6 3
5 6 7
10
C
B D E
E FD
B
A
6 3
5 6 7
10 8 9
C
B D E
E F FD
B
A
6
3
5 6 7
10 8 9 12
C
B D E
B
A
6
3
5 6 7
C
B D E
E F FD
B
A
6
3
5 6 7
10 8 9 12
(a) (b) (c) (d)
(e) (f) (g) (h)
图7, 1 1 单源最短路径的解空间树
从解空间树中我们得到源点 A到
网中其他顶点的最短路径的分析过程
中，使用了分支限界法 (Branch and
Bound)的思想。
分支限界法与回溯法的对比：
同,同为在问题的解空间树上搜索问
题解的方法。
异,
1,求解目标不同：回溯法的求解目标
是找出解空间树中满足约束条件的所有解，而
分支限界法的求解目标则是找出满足约束条件
的一个解，或是在满足约束条件的解中找出使
某一目标函数值达到极大或极小的解，即在某
种意义下的最优解。
2,对解空间树的搜索方式不同：
回溯法以深度优先的方式搜索解
空间树，而分支限界法则以广度优先或以
最小耗费（最大效益）优先的方式搜索解
空间树。
由于有双重循环，故对于含有 N个
顶点的有向网来说,Dijkstra算法总的
时间复杂度是 O(N2)。
7.5.2 多源最短路径问题与动态规划法
多源最短路径问题：
方法一：每次以一个顶点为源点，重
复执行 Dijkstra 算法 N次。
效率与 方法一 同阶，
但形式相对简单
方法二,Floyed算法
Floyed 算法从图的带权邻接矩阵 cost
出发，其基本思想是：
假设求从顶点 vi到 vj 的最短路径 。 如果从 vi到
vj有弧, 则从 vi到 vj存在一条长度为 cost[i,j]的
路径 。
该路径不一定是最短路径, 尚需进行 N次试探 。
首先考虑路径 (vi,v1,vj)是否存在 （ 即判断弧
(vi,v1)和 (v1,vj)是否存在 ） 。 如果存在, 则比较
其路径长度 。 取长度较短者为从 vi到 vj的中间顶点的
序号不大于 1的最短路径 。
假如在路径上再增加一个顶点 v2,即如果
(vi,…,v2)和 (v2,…,vj)分别是当前找到的中间顶
点的序号不大于 1 的最短路径, 那么,
(vi,…,v2,…,vj)就有可能是从 vi到 vj中间顶点的序
号不大于 2的最短路径 。 将它和已经得到的从 vi到 vj
中间顶点序号不大于 1的最短路径相比较, 从中选出
较小者做为中间顶点的序号不大于 2的最短路径 。
之后, 再增加一个顶点 v3,继续进行试探 。 依
此类推, …, 直至经过 N次比较, 最后求得的就是从
vi到 vj中间顶点的序号不大于 N的最短路径 。 因为有
向网中只有 N个顶点, 故该路径就是从 vi到 vj的最短
路径 。 按此方法, 可以同时求得各对顶点间的最短
路径 。
Floyed 算法中，新一步的结果总是
基于上一步的结果，所以每次运算都无需从
头做起，这正是动态规划 (Dynamic
Programming)算法的典型设计思想。
动态规划法与分治法 的对比：
同, 在解决问题时基于问题的划分：
将问题实例归纳为更小的、相似的子问题，
并通过求解子问题产生一个全局最优解。
异,
分治法中，各个子问题是独立的 (即不
包含公共的子问题 )，因此一旦递归地求出各
子问题的解后，便可自下而上地将子问题的解
合并成问题的解。要做许多不必要的重复工作。
动态规划法中，整个问题的最优解是由
各个子问题的最优解构成的。在求解过程中，
每个子解都是在前面的结果上得出的新的子解，
子解随着步骤的进行而逐步扩大，最后一步得
到完整的解。
7.6 本章小结
? 基本内容：
1,图的定义，有关术语；
2,图的四种存储结构；
3,图的两种遍历方法：深度优先遍
历和广度优先遍历；拓扑排序问题；
4,最小生成树；
5,图的最短路径问题；分支限界法
与动态规划法。
? 基本要求：
熟悉图的各种 存储结构 及其 构造算
法, 了解实际问题的求解效率与采用
何种存储结构和算法有密切联系 。
熟练掌握图的 两种搜索路径 的遍历：
遍历的 逻辑定义, 深度优先 搜索和 广
度优先 搜索的算法 。
在学习中应注意 图 的遍历算法与 树 的
遍历算法之间的 类似和差异 。 树的先根
遍历是一种深度优先搜索策略, 树的层
次遍历是一种广度优先搜索策略 。
理解实际 应用 中各种图的算法 。
学习并使用 动态规划 法与 分支限界 法
的思想 。
