1
8.1 图
8.2 图的存储结构
8.3 图的实现
8.4 图的遍历
8.5 最小生成树
8.6 最短路径
第 8章 图
2
８,1 图
一、图的基本概念
１,图,由结点集合及结点间的关系集合组成的一种数据结构。
记为 G＝ ( V,E )，其中,V是 G的 顶点 集合，是有穷非空集； E
是 G的 边 集合，是有穷集。
v1 v2
v3
v5v4
v1 v2
v3 v4
2,有向图,图 G中的每条边都是有方向的；
３,无向图,图 G中的每条边都是无方向的；
４,完全图,图 G任意两个顶点都有一条边相连接；
?若 n 个顶点的无向图有 n(n-1)/2 条边,称为 无向完全图
?若 n 个顶点的有向图有 n(n-1) 条边,称为 有向完全图
(a)有向图 (b)有向图 (c)无向完全图 (d)有向完全图
1
2 3
41
2 3
4
3
5,子图,设有两个图 G1＝ (V1,E1) 和 G2＝ (V2,E2)。若 V2 ?
V1 且 E2 ?E1,则称 图 G2 是 图 G1 的子图。
(a)图 1 (b)图２
７,路径,在图 G＝ (V,E)中,若从顶点 vi 出发,沿一些边经过
一顶点 vp1,vp2,…,vpm，到达顶点 vj。则称顶点序列 (vi,vp1,vp2,…,
vpm,vj ) 为从顶点 vi 到顶点 vj 的 路径 。
路径长度,非带权图 的 路径长度 是指此路径上 边的条数 ；
带权图 的 路径长度 是指路径上 各边的权之和 。
6,带权图,指边上带权的图。 其中 权 是指每条边标上具有与
该边相关的数据信息。
８,简单路径,路径上各顶点 v1,v2,...,vm 均不互相重复。
９,回路,若路径上第一个顶点 v1 与最后一个顶点 vm 重合，则
称这样的路径为 回路或环 。
4
10,连通图,在 无向 图中,若从顶点 v1到顶点 v2有路径,则称顶
点 v1与 v2是 连通 的。如果图中任意一对顶点都是连通的,则称此
图是 连通图 。
非连通图的极大连通子图 叫做 连通分量 。
11,强连通图,在 有向 图中,若对于每一对顶点 vi和 vj,都存在
一条从 vi到 vj和 从 vj到 vi的路径,则称此图是 强连通图 。
非强连通图的极大强连通子图 叫做 强连通分量 。
12,生成树,是一个 极小连通子图,它含有图中全部 n个顶点，但
只有 n-1条边 。
13,结点的度,结点 v的 度 是与它相关联的边的条数。记作 TD(v)。
在 有向图 中,结点的 度 等于该结点的 入度 与 出度 之和。其中结点
v 的 入度 是以 v 为 终点 的有向边的条数,记作 ID(v);结点 v 的
出度 是以 v 为 始点 的有向边的条数,记作 OD(v)。
14,邻接结点,若 (u,v) 是 E(G) 中的一条边，则称 u 与 v 互为 邻
接结点。
5
数据集合,由一组结点集合｛ vi ｝和一组边集合 {ej}组成。当为
带权图时每条边上权 wi构成权集合 {wi}。
操作集合：
(1)初始化 Initiate(G,n)
(2)插入结点 InsertVertex(G,vertex)
(3)插入边 InsertEdge(G,v1,v2,weight)
(4)删除边 DeleteEdge（ G,v1,v2)
(5)删除结点 DeeteVertex(G,vertex)
(6)第一个邻接结点 GetFirstVex(G,v)
(7)下一个邻接结点 GetNextVex(G,v1,v2)
二、图的抽象数据类型
6
8.2 图的存储结构
图的存储结构主要有邻接矩阵和邻接表两种。
一、图的邻接矩阵
1、无权值的有向图的邻接矩阵
设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图；
并且 A[i,j] = 1,如果 i 至 j 有一条有向边； A[I,j]=0,如果 i 至 j 没有一条有向边。
有向图 邻接矩阵
B
A D
C E ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
E
D
C
B
A
V
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00000
00010
10000
00000
11110
A
(b)
(a)
7
2、无权值的无向图的邻接矩阵
设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图；
并且 A[i,j]=1,如果 i 至 j 有一条无向边； A[I,j]=0,如果 i 至 j 没有一条无向边。
无向图 邻接矩阵
2
1 4
3
5
6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
????
?
???
???
???
?
080
070
807005040
50030
40020
30200
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6
5
4
3
2
1
V
(a) (b)
4020
30 50
70
80
3、有向图的加权邻接矩阵
设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图；
并且 A[i,j]=a,如果 i 至 j 有一条有向边且它的权值为 a。 A[i,j] = ‘空 或其它标
志；如果 i 至 j 没有一条有向边。
带权图 邻接矩阵
2
1 4
3 5
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
5
4
3
2
1
V
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00101
00011
10001
01001
11110
A
(b)
(a)
8
（ v1 v2 v3 v4 v5 ）
v1
v2
v3
v4
v5
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
0 1 1 1 0
分析 1,无向图的邻接矩阵是 对称 的；
分析 2,顶点 i的 度 ＝第 i 行 (列 ) 中 1 的个数 ；
特别,完全图 的邻接矩阵中，对角元素为 0，其余全 1。
顶点表,V=
例 1、无向图的邻接矩阵如何表示？
v1 v2
v3
v5v4
A 0 0 0 0 0
0 0 0
0 0 0
0 0 0
1
邻接矩阵,A=
9
例 2, 有向图的邻接矩阵如何表示？
分析 1,有向图的邻接矩阵 可能是不对称 的。
分析 2,顶点 vi的 出度 =第 i行元素之和, OD(vi )=?A[ i ][j ]
顶点 vi的 入度 =第 i列元素之和 。 ID(vi )=?A[ j ][i ]
顶点的 度 =第 i行元素之和 +第 i列元素之和,
即,TD( vi ) = OD( vi ) + ID( vi )
v1 v2
v3 v4
A 邻接矩阵,A=
( v1 v2 v3 v4 )
v1
v2
v3
v4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
注,在有向图的邻接矩阵中，
第 i行含义：以结点 vi为尾的弧 (即出度边）；
第 i列含义：以结点 vi为头的弧 (即入度边）。
顶点表：
1 1
1
1
10
容易实现图的操作，如：求某顶点的度、判断
顶点之间是否有边（弧）、找顶点的邻接点等等。
n个顶点需要 n*n个单元存储边 (弧 );空间效率
为 O(n2)。
例 3, 有权图（即 网络 ）的 邻接矩阵 如何表示？
v1 v2
v3
v4
A
v5
v6
5
48
97
5
5
61
3
以有向网为例：
邻接矩阵,∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
A =
( v1 v2 v3 v4 v5 v6 )
邻接矩阵法 优点：
邻接矩阵法 缺点：
顶点表：
5 7
4
8 9
5 6
5
3 1
∞ 5 ∞ 7 ∞
∞∞ 4 ∞ ∞ ∞
8 ∞ ∞ 9
∞∞ 5 ∞ ∞ 6
∞∞ ∞ 5 ∞ ∞
3 ∞ 1 ∞
v1
v2
v3
v4
v5
v6
对稀疏图而言尤其浪费空间。
11
二, 图的邻接表存储结构
B
A D
C E
(a)
0
1
2
3
4
A
B
C
D
E
0
data sorce
1
4 3 2
adj dest next
2
3
4
1
1 ∧
∧
∧
∧
(b)
4 ∧
1、图的邻接表
它是一种顺序存储与链式存储相结合的存储方法，顺序存
储部分用来保存图中顶点的信息，链式存储部分用来保存图中
边（或弧的信息）
有向图 邻接表
12
分析 1,对于 n个顶点 e条边的无向图,邻接表中除了 n个头结点
外，只有 2e个表结点,空间效率为 O(n+2e)。
若是稀疏图 (e<<n2)，则比邻接矩阵表示法 O(n2)省空间。
2、邻接表存储法的特点：
分析 2:在 有向图 中，邻接表中除了 n个头结点外，只有 e个表结点,
空间效率为 O(n+e)。 若是稀疏图，则比邻接矩阵表示法合适。
— 它其实是对邻接矩阵法的一种改进
怎样计算无向图顶点的度？
邻接表的 缺点：
邻接表的 优点：
TD(Vi)=单链表中链接的结点个数
空间效率高； 容易寻找顶点的邻接点；
判断两顶点间是否有边或弧，需搜索两
结点对应的单链表，没有邻接矩阵方便。
13
3、讨论：邻接表与邻接矩阵有什么异同之处？
1,联系,邻接表中每个链表对应于邻接矩阵中的一行，
链表中结点个数等于一行中非零元素的个数。
2,区别：
① 对于任一确定的无向图，邻接矩阵是唯一的（行列
号与顶点编号一致），但 邻接表不唯一 （链接次序
与顶点编号无关）。
② 邻接矩阵的空间复杂度为 O(n2),而邻接表的空间复
杂度为 O(n+e)。
3,用途：
邻接矩阵多用于稠密图的存储（ e接近 n(n-1)/2)；
而邻接表多用于稀疏图的存储（ e<<n2)
14
它是 有向图 的另一种链式结构。
思路,将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。
1、开设 弧结点,设 5个域 （每段弧是一个数据元素）
2、开设 顶点结点,设 3个域 （每个顶点也是一个数据元素）
tailvex headvex hlink tlink info
data, 顶点信息
Firstin, 以顶点为弧头的第一条弧结点
Firstout,以顶点为弧尾的第一条弧结点
data Firstin Firstout
顶点结点弧结点
三, 十字链表表示法
tailvex,弧尾顶点位置
headvex,弧头顶点位置
hlink,弧头相同的下一弧位置
tlink,弧尾相同的下一弧位置
info,弧信息
n个顶点的集合怎样储存？ 仍用顺序存储结构
15
v1 v2
v3 v4
2 0 2 ^^3
3 ^0 3 ^^1
例：画出有向图的十字链表。
十字链表优点,容易操作，如求顶点的入度、出度等。
FirstoutFirstindata顶点结点
infotlinkhlinkheadvextailvex弧结点
0 v1
1 v2
2 v3
3 v4
0
1
2
3
0 1 0 ^^2
此无权图未开第 4分量
空间复杂度和建表的时间复杂度都与邻接表相同 。
8.1 图
8.2 图的存储结构
8.3 图的实现
8.4 图的遍历
8.5 最小生成树
8.6 最短路径
第 8章 图
2
８,1 图
一、图的基本概念
１,图,由结点集合及结点间的关系集合组成的一种数据结构。
记为 G＝ ( V,E )，其中,V是 G的 顶点 集合，是有穷非空集； E
是 G的 边 集合，是有穷集。
v1 v2
v3
v5v4
v1 v2
v3 v4
2,有向图,图 G中的每条边都是有方向的；
３,无向图,图 G中的每条边都是无方向的；
４,完全图,图 G任意两个顶点都有一条边相连接；
?若 n 个顶点的无向图有 n(n-1)/2 条边,称为 无向完全图
?若 n 个顶点的有向图有 n(n-1) 条边,称为 有向完全图
(a)有向图 (b)有向图 (c)无向完全图 (d)有向完全图
1
2 3
41
2 3
4
3
5,子图,设有两个图 G1＝ (V1,E1) 和 G2＝ (V2,E2)。若 V2 ?
V1 且 E2 ?E1,则称 图 G2 是 图 G1 的子图。
(a)图 1 (b)图２
７,路径,在图 G＝ (V,E)中,若从顶点 vi 出发,沿一些边经过
一顶点 vp1,vp2,…,vpm，到达顶点 vj。则称顶点序列 (vi,vp1,vp2,…,
vpm,vj ) 为从顶点 vi 到顶点 vj 的 路径 。
路径长度,非带权图 的 路径长度 是指此路径上 边的条数 ；
带权图 的 路径长度 是指路径上 各边的权之和 。
6,带权图,指边上带权的图。 其中 权 是指每条边标上具有与
该边相关的数据信息。
８,简单路径,路径上各顶点 v1,v2,...,vm 均不互相重复。
９,回路,若路径上第一个顶点 v1 与最后一个顶点 vm 重合，则
称这样的路径为 回路或环 。
4
10,连通图,在 无向 图中,若从顶点 v1到顶点 v2有路径,则称顶
点 v1与 v2是 连通 的。如果图中任意一对顶点都是连通的,则称此
图是 连通图 。
非连通图的极大连通子图 叫做 连通分量 。
11,强连通图,在 有向 图中,若对于每一对顶点 vi和 vj,都存在
一条从 vi到 vj和 从 vj到 vi的路径,则称此图是 强连通图 。
非强连通图的极大强连通子图 叫做 强连通分量 。
12,生成树,是一个 极小连通子图,它含有图中全部 n个顶点，但
只有 n-1条边 。
13,结点的度,结点 v的 度 是与它相关联的边的条数。记作 TD(v)。
在 有向图 中,结点的 度 等于该结点的 入度 与 出度 之和。其中结点
v 的 入度 是以 v 为 终点 的有向边的条数,记作 ID(v);结点 v 的
出度 是以 v 为 始点 的有向边的条数,记作 OD(v)。
14,邻接结点,若 (u,v) 是 E(G) 中的一条边，则称 u 与 v 互为 邻
接结点。
5
数据集合,由一组结点集合｛ vi ｝和一组边集合 {ej}组成。当为
带权图时每条边上权 wi构成权集合 {wi}。
操作集合：
(1)初始化 Initiate(G,n)
(2)插入结点 InsertVertex(G,vertex)
(3)插入边 InsertEdge(G,v1,v2,weight)
(4)删除边 DeleteEdge（ G,v1,v2)
(5)删除结点 DeeteVertex(G,vertex)
(6)第一个邻接结点 GetFirstVex(G,v)
(7)下一个邻接结点 GetNextVex(G,v1,v2)
二、图的抽象数据类型
6
8.2 图的存储结构
图的存储结构主要有邻接矩阵和邻接表两种。
一、图的邻接矩阵
1、无权值的有向图的邻接矩阵
设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图；
并且 A[i,j] = 1,如果 i 至 j 有一条有向边； A[I,j]=0,如果 i 至 j 没有一条有向边。
有向图 邻接矩阵
B
A D
C E ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
E
D
C
B
A
V
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00000
00010
10000
00000
11110
A
(b)
(a)
7
2、无权值的无向图的邻接矩阵
设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图；
并且 A[i,j]=1,如果 i 至 j 有一条无向边； A[I,j]=0,如果 i 至 j 没有一条无向边。
无向图 邻接矩阵
2
1 4
3
5
6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
????
?
???
???
???
?
080
070
807005040
50030
40020
30200
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6
5
4
3
2
1
V
(a) (b)
4020
30 50
70
80
3、有向图的加权邻接矩阵
设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图；
并且 A[i,j]=a,如果 i 至 j 有一条有向边且它的权值为 a。 A[i,j] = ‘空 或其它标
志；如果 i 至 j 没有一条有向边。
带权图 邻接矩阵
2
1 4
3 5
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
5
4
3
2
1
V
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00101
00011
10001
01001
11110
A
(b)
(a)
8
（ v1 v2 v3 v4 v5 ）
v1
v2
v3
v4
v5
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
0 1 1 1 0
分析 1,无向图的邻接矩阵是 对称 的；
分析 2,顶点 i的 度 ＝第 i 行 (列 ) 中 1 的个数 ；
特别,完全图 的邻接矩阵中，对角元素为 0，其余全 1。
顶点表,V=
例 1、无向图的邻接矩阵如何表示？
v1 v2
v3
v5v4
A 0 0 0 0 0
0 0 0
0 0 0
0 0 0
1
邻接矩阵,A=
9
例 2, 有向图的邻接矩阵如何表示？
分析 1,有向图的邻接矩阵 可能是不对称 的。
分析 2,顶点 vi的 出度 =第 i行元素之和, OD(vi )=?A[ i ][j ]
顶点 vi的 入度 =第 i列元素之和 。 ID(vi )=?A[ j ][i ]
顶点的 度 =第 i行元素之和 +第 i列元素之和,
即,TD( vi ) = OD( vi ) + ID( vi )
v1 v2
v3 v4
A 邻接矩阵,A=
( v1 v2 v3 v4 )
v1
v2
v3
v4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
注,在有向图的邻接矩阵中，
第 i行含义：以结点 vi为尾的弧 (即出度边）；
第 i列含义：以结点 vi为头的弧 (即入度边）。
顶点表：
1 1
1
1
10
容易实现图的操作，如：求某顶点的度、判断
顶点之间是否有边（弧）、找顶点的邻接点等等。
n个顶点需要 n*n个单元存储边 (弧 );空间效率
为 O(n2)。
例 3, 有权图（即 网络 ）的 邻接矩阵 如何表示？
v1 v2
v3
v4
A
v5
v6
5
48
97
5
5
61
3
以有向网为例：
邻接矩阵,∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
∞∞∞ ∞ ∞ ∞
A =
( v1 v2 v3 v4 v5 v6 )
邻接矩阵法 优点：
邻接矩阵法 缺点：
顶点表：
5 7
4
8 9
5 6
5
3 1
∞ 5 ∞ 7 ∞
∞∞ 4 ∞ ∞ ∞
8 ∞ ∞ 9
∞∞ 5 ∞ ∞ 6
∞∞ ∞ 5 ∞ ∞
3 ∞ 1 ∞
v1
v2
v3
v4
v5
v6
对稀疏图而言尤其浪费空间。
11
二, 图的邻接表存储结构
B
A D
C E
(a)
0
1
2
3
4
A
B
C
D
E
0
data sorce
1
4 3 2
adj dest next
2
3
4
1
1 ∧
∧
∧
∧
(b)
4 ∧
1、图的邻接表
它是一种顺序存储与链式存储相结合的存储方法，顺序存
储部分用来保存图中顶点的信息，链式存储部分用来保存图中
边（或弧的信息）
有向图 邻接表
12
分析 1,对于 n个顶点 e条边的无向图,邻接表中除了 n个头结点
外，只有 2e个表结点,空间效率为 O(n+2e)。
若是稀疏图 (e<<n2)，则比邻接矩阵表示法 O(n2)省空间。
2、邻接表存储法的特点：
分析 2:在 有向图 中，邻接表中除了 n个头结点外，只有 e个表结点,
空间效率为 O(n+e)。 若是稀疏图，则比邻接矩阵表示法合适。
— 它其实是对邻接矩阵法的一种改进
怎样计算无向图顶点的度？
邻接表的 缺点：
邻接表的 优点：
TD(Vi)=单链表中链接的结点个数
空间效率高； 容易寻找顶点的邻接点；
判断两顶点间是否有边或弧，需搜索两
结点对应的单链表，没有邻接矩阵方便。
13
3、讨论：邻接表与邻接矩阵有什么异同之处？
1,联系,邻接表中每个链表对应于邻接矩阵中的一行，
链表中结点个数等于一行中非零元素的个数。
2,区别：
① 对于任一确定的无向图，邻接矩阵是唯一的（行列
号与顶点编号一致），但 邻接表不唯一 （链接次序
与顶点编号无关）。
② 邻接矩阵的空间复杂度为 O(n2),而邻接表的空间复
杂度为 O(n+e)。
3,用途：
邻接矩阵多用于稠密图的存储（ e接近 n(n-1)/2)；
而邻接表多用于稀疏图的存储（ e<<n2)
14
它是 有向图 的另一种链式结构。
思路,将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。
1、开设 弧结点,设 5个域 （每段弧是一个数据元素）
2、开设 顶点结点,设 3个域 （每个顶点也是一个数据元素）
tailvex headvex hlink tlink info
data, 顶点信息
Firstin, 以顶点为弧头的第一条弧结点
Firstout,以顶点为弧尾的第一条弧结点
data Firstin Firstout
顶点结点弧结点
三, 十字链表表示法
tailvex,弧尾顶点位置
headvex,弧头顶点位置
hlink,弧头相同的下一弧位置
tlink,弧尾相同的下一弧位置
info,弧信息
n个顶点的集合怎样储存？ 仍用顺序存储结构
15
v1 v2
v3 v4
2 0 2 ^^3
3 ^0 3 ^^1
例：画出有向图的十字链表。
十字链表优点,容易操作，如求顶点的入度、出度等。
FirstoutFirstindata顶点结点
infotlinkhlinkheadvextailvex弧结点
0 v1
1 v2
2 v3
3 v4
0
1
2
3
0 1 0 ^^2
此无权图未开第 4分量
空间复杂度和建表的时间复杂度都与邻接表相同 。
