第 六 章 图
在线性表中,数据元素之间仅有线性关系,除第一个元素
外每个数据元素只有一个直接前趋,除最后一个元素外,每个
数据元素只有一个直接后继, 在树形结构中,数据元素之间有
明显的层次关系,每一层上的数据元素可能和下一层中多个元
素相关,但只能和上一层中一个元素相关, 而在图形结构中,
任意两个数据元素之间都可能相关,即结点之间的关系可以是
任意的, 所以图是一种较线性表和树更为复杂的数据结构,其
应用也极为广泛,如在语言学 ﹑ 逻辑学 ﹑ 物理 ﹑ 化学 ﹑ 电讯工
程 ﹑ 计算机科学及数学的某些分支,均可采用图作为研究和分
析问题的工具, 在此主要讨论图的一些基本概念和术语,及图
的存储结构和图的若干操作,
6, 1 基本概念
图是一种数据结构,它的形式化定义为, ),( EVG ?
其中,
? ? ? ?),(),(,,VvvvvpvvEd a t a o b j e c tvvV jijiji ???????
在上面 定义中,数据元素 v 叫做顶点,V 是顶点的非空有限
集合 ;E 是两个顶点之间的关系的集合,若 Evv
ji ???,
,且
????? ijji vvvv,,,则 ?? ji vv,表示从 iv 到 jv 的一条弧
iv 叫做弧尾或初始顶点,jv 叫做弧头或终端顶点, 并称顶点
jv
邻接于顶点
iv,或称顶点 iv 邻接到顶点 jv,此时的图称为
有向图,如下面各图均为有向图,
1
3
2
4
1)( Ga
1
3
)(b
1 1 2
3 44
1
3
对于有向图 (a)可表成
? ?43211,,,)( vvvvGV ?
?
?
?
?
?
?
????
?????
1443
3121
1,,,
,,,,)(
vvvv
vvvvGE
若 必有Evv
ji ???,Evv ij ???,
即 E 是对称的,则以无序对
),( ji vv 代替有序对 ?? ji vv,和 ?? ij vv,,并以 ),( ji vv 表示 iv
和 jv 之间的一条边,此时的图叫无向图,如下所示,
2)( Gb
1
4
2
5
3
)(c
1 2
5
3
1
4
1 2
5
1
4
3
2
5
对于无向图可表成, ? ?
543212,,,,)( vvvvvGV ?
? ?),(),,(),,(),,(),,(),,()( 5343523241212 vvvvvvvvvvvvGE ?
在无向图中,若边 Evv
ji ?),(
,则称顶点 iv 和 jv 互为邻接点,
即 iv 和 jv 相邻接,边 ),(
ji vv
依附于顶点 iv 和 jv,或者说 ),(
ji vv和顶点
iv 和 jv 相关联,
在图中,顶点数目用 n表示,如 1G 的 n=4,2G 的 n=5.
用 e表示弧或边的数目,如 1G 中弧的数目 e=4,
2G
中边的
数目 e=6.
若图中,且Evv
ji ???,ji vv ?
,说明图中顶点没有到其
自身的弧或边, 在下面的讨论中均认为图中顶点没有到其
自身的弧或边, 则对于无向图,e的取值范围是 0到 n (n-1)/2
当 e= n (n-1)/2时的无 向图叫 无 向完全图, 对于有向图,e的
取值范围是 0到 n (n-1),当 e= n (n-1)时的有 向图叫 有 向完全
图,
对于无向图,顶点 iv 的度是和 iv 相关联的边的数目,记
为 )(
ivTD
,例如下面无向图中,
2)( Gb
1
4
2
5
3
3)( 3 ?vTD,对于有向图,
1
3
2
4
1)( Ga
以顶点 iv 为头的弧的数目叫 iv 的入度
记为 )(
ivID,对于右边有向图,1)( 1 ?vID
以顶点 iv 为尾的弧的数目叫 iv 的出度
记为 )(
ivOD
,对于右边有向图,2)(
1 ?vOD
顶点 iv 的度为 )()()(
iii vODvIDvTD ??
,对于无向图或有向
图,均有
?
?
? n
i
ivTDe
1
)(21
6, 2 图的存储结构
6.2.1邻接矩阵
邻接矩阵是图的一种顺序存储表示,它是利用一个矩
阵来表示图中顶点之间的关系,对于一个具有 n个顶点的
图 ),( EVG ? 来说,其 邻接矩阵是一个 n阶方阵,且满足,
? ?
??
??
0
1,jiA
若 ),(,
jiji vvorvv ??
是 )(GE 的弧或边,
若 ),(,
jiji vvorvv ??
不是 )(GE 中的弧或边,
下面有向图和无向图的 邻接矩阵分别为,
2G
1
4
2
5
3
1
3
2
4
1G
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110
1
A
1v
1v
2v
2v
3v
3v
4v
4v
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
2
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v
由邻接矩阵易于判定任意两个顶点之间是否有边或弧
相连,并容易求得各个顶点的度, 对于无向图,顶点 iv
的度是 邻接矩阵中第 i 行 (或第 i 列 )的元素值之和,即,
? ? ? ???
??
?? n
j
n
j
i ijAjiAvTD
11
,,)(,例如,对于 2G
2G
1
4
2
5
3
及
2A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
2
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v ? ? ? ?
3
3,,3)(
5
1
5
1
3
?
?? ??
?? jj
jAjAvTD
对于 有 向图,第 i 行的元素
值之和为顶点 iv 的出度 )(
ivOD
第 i 列的元素值之和为顶
点 iv 的入度 )(
ivID,例如,对
于 1G 及 1A1
3
2
4
1G ?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110
1A
1v
1v
2v
2v
3v
3v
4v
4v
312
)()()( 111
???
?? vIDvODvTD
6.2.2 邻接表
邻接表是图的一种链式分配和顺序分配相给合的存储
结构,先以下面的无向图说明邻接表的结构形式,
2G
1
4
2
5
3
?1
?2
?3
?4
?5
先建立一指针类型向量,以存储 n(=5)个表头结
点,向量的下标指示了顶点的序号, 链表部分
由 n个 链表 (n为 顶点个数 ),每个 顶点对应一个链表
2 ?4?
每个链表由一个 表头结 点和若干个 表结 点
组成,表头结 点用来指示第 个顶点i
iv 所对应的链表, 表结 点由顶点域
和链域组成,顶点域指示了与 iv
相邻接的顶点的序号,故一个表结
点代表一条依附于 iv 的边 ; 链域指示了依附于 iv 的另一条
边的 表结 点,从而第 i 个链表就表示了依附于顶点 iv 的所
有的边,
3 ?5? 1
4 ?5? 2
?3? 1
?3? 2
在 无向图的邻接表中,顶点 iv 的度即为第 i 个链
表 中的 表结 点个数 (即不包括 表头结 点 ).
以下面的有向图说明其邻接表的结构形式,
邻接表
1
3
2
4
1G
?1
?2
?3
?4
2 ?3?
?4?
?1?
可见 其结构
形式与无向图的邻接表是一样的, 所不同的是
第 i 个链表表示了从顶点
iv
出发的所有的弧,
因此,第 i 个链 表 中的 表结 点个数 (即不包括
表头结 点 )是顶点 iv 出度,而顶点 iv 的入
度却需找遍除第 i 个链 表外的所有其它
链 表,统计出在这些 链 表中的 顶点 iv 的
个数即为其的入度, 如对于 1v 其出度
为 2,其入度为 1,故其度为 3,显然由
邻接表确定有向图各个顶点的出度较
为方便,但确定各个顶点的入度较为
费事,因此引出逆邻接表,
?1
?2
?3
?4
?4?
?1?
?3?
?1?
逆邻接表 逆 邻接表
中第 i 个链表表示了以顶点 iv 为弧头的所有的弧,其
表结 点个数 (即不包括 表头结 点 )是顶点 iv 的入度,
6,3 图的遍历
从图中某一顶点出发访遍图中其余顶点,且每个顶点
仅被访问一次,这一过程叫图的遍历,
由于图中任一顶点都可能和其余的顶点相邻接,故图
的遍历比树的遍历要复杂的多, 表现之一,是从某一顶点
出发,沿某条路经搜索后,又回到出发的顶点上,为避免
同一顶点被访问多次,在遍历图的过程中,必须记下每个
已被访问过的顶点, 下面介绍两种通常用的遍历图的方法
深度优先搜索法和广度优先搜索法, 这两种方法对无向图
和有向图都是适用的,
一 ﹑ 深度优先搜索法
深度优先搜索遍历图类似于树的前序遍历,其过程是
设初态为图中所有顶点均未被访问过,则从图中某个顶点
iv 出发,访问此顶点,然后依次从 iv 的 未被访问的邻接点
出发深度优先遍历图,直到图中所有和 有路经相通的顶点iv
都被访问到 ; 若一次遍历后还有顶点未被访问到,则另选一
个未被访问的顶点作起始点,重复上述过程,直至所有顶点
G
1v
2v 3v
4v 5v
8v
6v 7v
选 1v 为初始 顶点,则都被访问到, 下面举例说明,
1v 2,v 4,v 8,v 5,v
由于 2v 已 被访问过,故再任选一未被访
问过的
3,v
1v 邻接点,进行 深度优先搜索
6,v 7,v
对图 G 进行 深度优先搜索遍历的结果,
即 顶点序列是不唯一的, 但从图 G 的
邻接矩阵或邻接表进行 深度优先搜索,
则其结果是唯一的, 例如对左边 A阵
进行 深度优先搜索遍历的结果为,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00011000
00100100
01000100
10000010
10000010
01100001
00011001
00000110
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v
6v
6v
7v
7v
8v
8v
1v 2,v 4,v 8,v 5,v 3,v 6,v 7,v
对图 G 的邻接表进行 深度优先搜索的
结果请同学自己完成,
对于有向图进行深度优先搜索遍历的过程与无向图
基本一至,只是对有向图的搜索路经应沿箭头的方向进
行,
一 ﹑ 广度优先搜索法
图的广度优先搜索法遍历类似于树的按层次遍历,其
过程如下, 从图中某顶点
iv
出发,访问此顶点,然后依次
访问与 iv 相邻接 (对于有向图 则为 邻接于 iv )的所有未被访
问过的 邻接 顶点,再从这些 邻接 顶点出发 广度优先搜索
遍历图,直到所有已被访问的 顶点的 邻接 点都被 访问到,
若图中尚有 顶点未被 访问,则另选其中任一 顶点作起始
点,重复上述过程,直到图中所有顶点都被 访问到为止,
G
1v
2v 3v
4v 5v
8v
6v 7v
图 G 的 广度优先遍历的 顶点序列为,
1v 2,v 3,v 4,v 5,v 6,v 7,v 8,v
对图 进行 广度优先搜索遍历的结果,即 顶点序列是不唯G
一的,但从图 G 的邻接矩阵或邻接表进行 广度优先搜索,
则其结果是唯一的, 例如对下面 A阵进行 广度优先搜索
遍历的结果为,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00011000
00100100
01000100
10000010
10000010
01100001
00011001
00000110
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v
6v
6v
7v
7v
8v
8v
1v 2,v 3,v 4,v 5,v 6,v 7,v 8,v
对图 G 的邻接表进行 广度优先搜
索遍历的 结果请同学自己完成,
课外习题
教材 P.169第 1题 (另要求由邻接表写出 广度优先搜索遍历
和深度优先搜索遍历的结果 ),
第 2题 (另要求每个顶点的度 ﹑ 由 邻接矩阵和邻接
表给出两种 遍历的结果 ).
在线性表中,数据元素之间仅有线性关系,除第一个元素
外每个数据元素只有一个直接前趋,除最后一个元素外,每个
数据元素只有一个直接后继, 在树形结构中,数据元素之间有
明显的层次关系,每一层上的数据元素可能和下一层中多个元
素相关,但只能和上一层中一个元素相关, 而在图形结构中,
任意两个数据元素之间都可能相关,即结点之间的关系可以是
任意的, 所以图是一种较线性表和树更为复杂的数据结构,其
应用也极为广泛,如在语言学 ﹑ 逻辑学 ﹑ 物理 ﹑ 化学 ﹑ 电讯工
程 ﹑ 计算机科学及数学的某些分支,均可采用图作为研究和分
析问题的工具, 在此主要讨论图的一些基本概念和术语,及图
的存储结构和图的若干操作,
6, 1 基本概念
图是一种数据结构,它的形式化定义为, ),( EVG ?
其中,
? ? ? ?),(),(,,VvvvvpvvEd a t a o b j e c tvvV jijiji ???????
在上面 定义中,数据元素 v 叫做顶点,V 是顶点的非空有限
集合 ;E 是两个顶点之间的关系的集合,若 Evv
ji ???,
,且
????? ijji vvvv,,,则 ?? ji vv,表示从 iv 到 jv 的一条弧
iv 叫做弧尾或初始顶点,jv 叫做弧头或终端顶点, 并称顶点
jv
邻接于顶点
iv,或称顶点 iv 邻接到顶点 jv,此时的图称为
有向图,如下面各图均为有向图,
1
3
2
4
1)( Ga
1
3
)(b
1 1 2
3 44
1
3
对于有向图 (a)可表成
? ?43211,,,)( vvvvGV ?
?
?
?
?
?
?
????
?????
1443
3121
1,,,
,,,,)(
vvvv
vvvvGE
若 必有Evv
ji ???,Evv ij ???,
即 E 是对称的,则以无序对
),( ji vv 代替有序对 ?? ji vv,和 ?? ij vv,,并以 ),( ji vv 表示 iv
和 jv 之间的一条边,此时的图叫无向图,如下所示,
2)( Gb
1
4
2
5
3
)(c
1 2
5
3
1
4
1 2
5
1
4
3
2
5
对于无向图可表成, ? ?
543212,,,,)( vvvvvGV ?
? ?),(),,(),,(),,(),,(),,()( 5343523241212 vvvvvvvvvvvvGE ?
在无向图中,若边 Evv
ji ?),(
,则称顶点 iv 和 jv 互为邻接点,
即 iv 和 jv 相邻接,边 ),(
ji vv
依附于顶点 iv 和 jv,或者说 ),(
ji vv和顶点
iv 和 jv 相关联,
在图中,顶点数目用 n表示,如 1G 的 n=4,2G 的 n=5.
用 e表示弧或边的数目,如 1G 中弧的数目 e=4,
2G
中边的
数目 e=6.
若图中,且Evv
ji ???,ji vv ?
,说明图中顶点没有到其
自身的弧或边, 在下面的讨论中均认为图中顶点没有到其
自身的弧或边, 则对于无向图,e的取值范围是 0到 n (n-1)/2
当 e= n (n-1)/2时的无 向图叫 无 向完全图, 对于有向图,e的
取值范围是 0到 n (n-1),当 e= n (n-1)时的有 向图叫 有 向完全
图,
对于无向图,顶点 iv 的度是和 iv 相关联的边的数目,记
为 )(
ivTD
,例如下面无向图中,
2)( Gb
1
4
2
5
3
3)( 3 ?vTD,对于有向图,
1
3
2
4
1)( Ga
以顶点 iv 为头的弧的数目叫 iv 的入度
记为 )(
ivID,对于右边有向图,1)( 1 ?vID
以顶点 iv 为尾的弧的数目叫 iv 的出度
记为 )(
ivOD
,对于右边有向图,2)(
1 ?vOD
顶点 iv 的度为 )()()(
iii vODvIDvTD ??
,对于无向图或有向
图,均有
?
?
? n
i
ivTDe
1
)(21
6, 2 图的存储结构
6.2.1邻接矩阵
邻接矩阵是图的一种顺序存储表示,它是利用一个矩
阵来表示图中顶点之间的关系,对于一个具有 n个顶点的
图 ),( EVG ? 来说,其 邻接矩阵是一个 n阶方阵,且满足,
? ?
??
??
0
1,jiA
若 ),(,
jiji vvorvv ??
是 )(GE 的弧或边,
若 ),(,
jiji vvorvv ??
不是 )(GE 中的弧或边,
下面有向图和无向图的 邻接矩阵分别为,
2G
1
4
2
5
3
1
3
2
4
1G
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110
1
A
1v
1v
2v
2v
3v
3v
4v
4v
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
2
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v
由邻接矩阵易于判定任意两个顶点之间是否有边或弧
相连,并容易求得各个顶点的度, 对于无向图,顶点 iv
的度是 邻接矩阵中第 i 行 (或第 i 列 )的元素值之和,即,
? ? ? ???
??
?? n
j
n
j
i ijAjiAvTD
11
,,)(,例如,对于 2G
2G
1
4
2
5
3
及
2A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
2
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v ? ? ? ?
3
3,,3)(
5
1
5
1
3
?
?? ??
?? jj
jAjAvTD
对于 有 向图,第 i 行的元素
值之和为顶点 iv 的出度 )(
ivOD
第 i 列的元素值之和为顶
点 iv 的入度 )(
ivID,例如,对
于 1G 及 1A1
3
2
4
1G ?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110
1A
1v
1v
2v
2v
3v
3v
4v
4v
312
)()()( 111
???
?? vIDvODvTD
6.2.2 邻接表
邻接表是图的一种链式分配和顺序分配相给合的存储
结构,先以下面的无向图说明邻接表的结构形式,
2G
1
4
2
5
3
?1
?2
?3
?4
?5
先建立一指针类型向量,以存储 n(=5)个表头结
点,向量的下标指示了顶点的序号, 链表部分
由 n个 链表 (n为 顶点个数 ),每个 顶点对应一个链表
2 ?4?
每个链表由一个 表头结 点和若干个 表结 点
组成,表头结 点用来指示第 个顶点i
iv 所对应的链表, 表结 点由顶点域
和链域组成,顶点域指示了与 iv
相邻接的顶点的序号,故一个表结
点代表一条依附于 iv 的边 ; 链域指示了依附于 iv 的另一条
边的 表结 点,从而第 i 个链表就表示了依附于顶点 iv 的所
有的边,
3 ?5? 1
4 ?5? 2
?3? 1
?3? 2
在 无向图的邻接表中,顶点 iv 的度即为第 i 个链
表 中的 表结 点个数 (即不包括 表头结 点 ).
以下面的有向图说明其邻接表的结构形式,
邻接表
1
3
2
4
1G
?1
?2
?3
?4
2 ?3?
?4?
?1?
可见 其结构
形式与无向图的邻接表是一样的, 所不同的是
第 i 个链表表示了从顶点
iv
出发的所有的弧,
因此,第 i 个链 表 中的 表结 点个数 (即不包括
表头结 点 )是顶点 iv 出度,而顶点 iv 的入
度却需找遍除第 i 个链 表外的所有其它
链 表,统计出在这些 链 表中的 顶点 iv 的
个数即为其的入度, 如对于 1v 其出度
为 2,其入度为 1,故其度为 3,显然由
邻接表确定有向图各个顶点的出度较
为方便,但确定各个顶点的入度较为
费事,因此引出逆邻接表,
?1
?2
?3
?4
?4?
?1?
?3?
?1?
逆邻接表 逆 邻接表
中第 i 个链表表示了以顶点 iv 为弧头的所有的弧,其
表结 点个数 (即不包括 表头结 点 )是顶点 iv 的入度,
6,3 图的遍历
从图中某一顶点出发访遍图中其余顶点,且每个顶点
仅被访问一次,这一过程叫图的遍历,
由于图中任一顶点都可能和其余的顶点相邻接,故图
的遍历比树的遍历要复杂的多, 表现之一,是从某一顶点
出发,沿某条路经搜索后,又回到出发的顶点上,为避免
同一顶点被访问多次,在遍历图的过程中,必须记下每个
已被访问过的顶点, 下面介绍两种通常用的遍历图的方法
深度优先搜索法和广度优先搜索法, 这两种方法对无向图
和有向图都是适用的,
一 ﹑ 深度优先搜索法
深度优先搜索遍历图类似于树的前序遍历,其过程是
设初态为图中所有顶点均未被访问过,则从图中某个顶点
iv 出发,访问此顶点,然后依次从 iv 的 未被访问的邻接点
出发深度优先遍历图,直到图中所有和 有路经相通的顶点iv
都被访问到 ; 若一次遍历后还有顶点未被访问到,则另选一
个未被访问的顶点作起始点,重复上述过程,直至所有顶点
G
1v
2v 3v
4v 5v
8v
6v 7v
选 1v 为初始 顶点,则都被访问到, 下面举例说明,
1v 2,v 4,v 8,v 5,v
由于 2v 已 被访问过,故再任选一未被访
问过的
3,v
1v 邻接点,进行 深度优先搜索
6,v 7,v
对图 G 进行 深度优先搜索遍历的结果,
即 顶点序列是不唯一的, 但从图 G 的
邻接矩阵或邻接表进行 深度优先搜索,
则其结果是唯一的, 例如对左边 A阵
进行 深度优先搜索遍历的结果为,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00011000
00100100
01000100
10000010
10000010
01100001
00011001
00000110
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v
6v
6v
7v
7v
8v
8v
1v 2,v 4,v 8,v 5,v 3,v 6,v 7,v
对图 G 的邻接表进行 深度优先搜索的
结果请同学自己完成,
对于有向图进行深度优先搜索遍历的过程与无向图
基本一至,只是对有向图的搜索路经应沿箭头的方向进
行,
一 ﹑ 广度优先搜索法
图的广度优先搜索法遍历类似于树的按层次遍历,其
过程如下, 从图中某顶点
iv
出发,访问此顶点,然后依次
访问与 iv 相邻接 (对于有向图 则为 邻接于 iv )的所有未被访
问过的 邻接 顶点,再从这些 邻接 顶点出发 广度优先搜索
遍历图,直到所有已被访问的 顶点的 邻接 点都被 访问到,
若图中尚有 顶点未被 访问,则另选其中任一 顶点作起始
点,重复上述过程,直到图中所有顶点都被 访问到为止,
G
1v
2v 3v
4v 5v
8v
6v 7v
图 G 的 广度优先遍历的 顶点序列为,
1v 2,v 3,v 4,v 5,v 6,v 7,v 8,v
对图 进行 广度优先搜索遍历的结果,即 顶点序列是不唯G
一的,但从图 G 的邻接矩阵或邻接表进行 广度优先搜索,
则其结果是唯一的, 例如对下面 A阵进行 广度优先搜索
遍历的结果为,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00011000
00100100
01000100
10000010
10000010
01100001
00011001
00000110
A
1v
1v
2v
2v
3v
3v
4v
4v
5v
5v
6v
6v
7v
7v
8v
8v
1v 2,v 3,v 4,v 5,v 6,v 7,v 8,v
对图 G 的邻接表进行 广度优先搜
索遍历的 结果请同学自己完成,
课外习题
教材 P.169第 1题 (另要求由邻接表写出 广度优先搜索遍历
和深度优先搜索遍历的结果 ),
第 2题 (另要求每个顶点的度 ﹑ 由 邻接矩阵和邻接
表给出两种 遍历的结果 ).
