,数据结构,
第七章 (上 )
数据结构
tjm
第七章 图
7.1 图的定义和术语
7.2 图的存储结构
7.2.1 数组表示法
7.2.2 邻接表
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的连通性问题
7.4.3 最小生成树
7.5 有向无环图及其应用
7.5.1 拓扑排序
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
7.6.2 每一对顶点之间的最短路径
数据结构
tjm
图的类型定义参见 P156
7.1 图的定义和术语
图的定义,是一种多对多的结构关系，每个元素
可以有零个或多个直接前趋；零个或多个直接后
继。图是由顶点集合 (vertex)及顶点间的关系集
合组成的一种数据结构：
Graph＝ ( V,R )
其中 V = { v | v ? 某个数据对象 }
是顶点的有穷非空集合；
R ={VR}={(v,w) | v,w ? V }
数据结构
tjm
基本术语：
有向图与无向图 在有向图中，顶点对 <v,w>是
有序的。在无向图中，顶点对 (x,y)是无序的。
5
3
6
7
2
1
4
有向图
V={1,2,3,4,5,6,7}
VR={<1,3>,<1,2>,<3,7>,<3,6>,<2,5>,<2,6>,
<2,4>,<5,7>,<6,7>}
有向边又可称为 弧,<vi,vj>
中 vi称为 狐尾 或初始点,vj
称为 狐头 或终端点。
数据结构
tjm
无向图
5
3
6 7
2
1
4
V={1,2,3,4,5,6,7}
VR={(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(
6,7),(5,6),(1,5),(1,7) }
数据结构
tjm
邻接点及关联
若无向图中存在边 (v,u)，则称顶点 v
和 u互为邻接点；边 (v,u)依附于顶点
v和 u；或者说边 (v,u)和顶点 v和 u相
关联。
顶点的度、入度、出度
在无向图中：
顶点 V的度 = 与 V相关联的边的数目
在有向图中：
顶点 V的出度 =以 V为狐尾的有向边数
顶点 V的入度 =以 V为狐头的有向边数
顶点 V的度 = V的出度 +V的入度
V0
V4V3
V1
V2
V0 V1
V2 V3
数据结构
tjm
路径、回路
无向图 G =（ V,{E}）中的顶点序列 v1,v2,…,vk,
若 (vi,vi+1)?E( i=1,2,… k-1),v =v1,u =vk,则
称该序列是从顶点 v到顶点 u的路径。
若 v=u，则称该序列为回路。
在图 G1中,V0,V1,V2,V3 是 V0到 V3的路径。
V0,V1,V2,V3,V0是回路。
V0
V4V3
V1
V2
例：
数据结构
tjm
有向图 G2
V0 V1
V2 V3
在图 G2中,V0,V2,V3 是 V0到 V3的路径。
V0,V2,V3,V0是回路。
有向图 G =（ V,{E}）中的顶点序列 v1,v2,…,vk,
若 <vi,vi+1>?E (i=1,2,… k-1),v =v1,u =vk,则
称该序列是从顶点 v到顶点 u的路径。
若 v=u，则称该序列为回路。
例：
数据结构
tjm
在一条路径中,若除起点和终点外,所有顶点各不
相同,则称该路径为简单路径。
由简单路径组成的回路称为简单回路。
在图 G1中,V0,V1,V2,V3 是简单路径。
V0,V1,V2,V4,V1不是简单路径。
在图 G2中,V0,V2,V3,V0是简单回路。
无向图 G1 有向图 G2
V0
V4V3
V1
V2
V0 V1
V2 V3
简单路径和简单回路
数据结构
tjm
非
连
通
图
连
通
图
强
连
通
图
非
强
连
通
图
V0 V1
V2 V3
V0
V4V3
V1
V2
V0 V1
V2 V3
V0
V2V3
V1
V5
V4
连通图（强连通图）
在无（有）向图 G=( V,{E} )中，若对任何两个顶
点 v,u 都存在从 v 到 u 的路径，则称 G是连通图
（强连通图）。
数据结构
tjm
(a) (b) (c)
V0
V4V3
V1
V2
V0
V4V3
V1
V2
V0
V4V3
V1
V2
子图
设有两个图 G=（ V,{E}）,G1=（ V1,{E1}），
若 V1? V,E1 ? E，则称 G1是 G的子图。
例,(b),(c) 是 (a) 的子图
权
某些图的边具有与它相关的数,称之为权。
这种带权图叫做网络。
数据结构
tjm
连通分量（强连通分量）
非
连
通
图
V0
V2V3
V1
V5
V4
无向图 G 的极大连通子图称为 G的连通分量。
极大连通子图意思是：该子图是 G 连通子图，将 G
的任何不在该子图中的顶点加入，子图不再连通。
V0
V2V3
V1
V5
V4
连通分量
数据结构
tjm
有向图 G 的极大强连通子图称为 G的强连通分量。
极大强连通子图意思是：该子图是 G的强连通子图
，将 D的任何不在该子图中的顶点加入，子图不再
是强连通的。 强连通分量
V0 V1
V2 V3
V0
V2 V3
V1
权与网
图中边或弧所具有的相关数称为权。表明从
一个顶点到另一个顶点的距离或耗费。 带权
的图称为 网 。
数据结构
tjm
极小连通子图,该子图是 G 的连通子图，在该子
图中删除任何一条边，子图不再连通。
包含无向图 G 所有顶点的极小连通子图称为 G 的
生成树。对非连通图，则称由各个连通分量的生
成树的集合为非连通图的生成森林。
连通图 G1 G1的生成树
V0
V4V3
V1
V2
V0
V4V3
V1
V2
V0
V4
V3 V1
V2
生成树和生成森林
图的几种基本操作参见 P158。
数据结构
tjm
?
?
? ???
?
，其它
或若
0
Ev,v)v,(v1,
],[ jijijiA
例：
G1
2
4
1
3
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110?
?
?
?
????
7.2.1 数组表示法
邻接矩阵,表示顶点间相联关系的矩阵。
定义：设 G=(V,{E})是有 n?1个顶点的图,G的邻接
矩阵 A是具有以下性质的 n阶方阵,
数据结构
tjm
例,1
5
3
2
4 G2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
???? ?
?
?
?
?
?
?
?
?
?
???
?
，其它
或若 Ev,v)v,(v,
],[ jijiijjiA
?
网的邻接矩
阵可定义为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
6183
624
127
845
375
???? ?
?
?
?
?
?
例,1
4
5
2
3
7
5
3
1
8
6
4
2
数据结构
tjm
邻接矩阵类型定义,
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN} GraphKind;
typedef struct ArcCell
{ VRType adj;
InfoType * info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
typedef struct
{ VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
数据结构
tjm
adjvex nextarc
vexdata firstarc
邻接表的类型定义参见 P163。
7.2.2 邻接表
实现：为图中每个顶点建立一个单链表，第 i个单
链表中的结点表示依附于顶点 Vi的边（有向图中指
以 Vi为尾的弧）。
例：
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
3 2
4
1
^
^
^
^
adjvex nextarc
数据结构
tjm
例,a
e
c
b
d G2
1
2
3
4
a
c
d
b
vexdata firstarc
4
2
1
2 ^
^
^
adjvexnextarc
5 e
4
3 5 ^1
5
3
2 3 ^
数据结构
tjm
例：
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
4
1 ^
1 ^
^
3 ^
adjvex nextarc
逆邻接表：有向图中对每个结点建立以 Vi为弧头
的弧的单链表。
第七章 (上 )
数据结构
tjm
第七章 图
7.1 图的定义和术语
7.2 图的存储结构
7.2.1 数组表示法
7.2.2 邻接表
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的连通性问题
7.4.3 最小生成树
7.5 有向无环图及其应用
7.5.1 拓扑排序
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
7.6.2 每一对顶点之间的最短路径
数据结构
tjm
图的类型定义参见 P156
7.1 图的定义和术语
图的定义,是一种多对多的结构关系，每个元素
可以有零个或多个直接前趋；零个或多个直接后
继。图是由顶点集合 (vertex)及顶点间的关系集
合组成的一种数据结构：
Graph＝ ( V,R )
其中 V = { v | v ? 某个数据对象 }
是顶点的有穷非空集合；
R ={VR}={(v,w) | v,w ? V }
数据结构
tjm
基本术语：
有向图与无向图 在有向图中，顶点对 <v,w>是
有序的。在无向图中，顶点对 (x,y)是无序的。
5
3
6
7
2
1
4
有向图
V={1,2,3,4,5,6,7}
VR={<1,3>,<1,2>,<3,7>,<3,6>,<2,5>,<2,6>,
<2,4>,<5,7>,<6,7>}
有向边又可称为 弧,<vi,vj>
中 vi称为 狐尾 或初始点,vj
称为 狐头 或终端点。
数据结构
tjm
无向图
5
3
6 7
2
1
4
V={1,2,3,4,5,6,7}
VR={(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(
6,7),(5,6),(1,5),(1,7) }
数据结构
tjm
邻接点及关联
若无向图中存在边 (v,u)，则称顶点 v
和 u互为邻接点；边 (v,u)依附于顶点
v和 u；或者说边 (v,u)和顶点 v和 u相
关联。
顶点的度、入度、出度
在无向图中：
顶点 V的度 = 与 V相关联的边的数目
在有向图中：
顶点 V的出度 =以 V为狐尾的有向边数
顶点 V的入度 =以 V为狐头的有向边数
顶点 V的度 = V的出度 +V的入度
V0
V4V3
V1
V2
V0 V1
V2 V3
数据结构
tjm
路径、回路
无向图 G =（ V,{E}）中的顶点序列 v1,v2,…,vk,
若 (vi,vi+1)?E( i=1,2,… k-1),v =v1,u =vk,则
称该序列是从顶点 v到顶点 u的路径。
若 v=u，则称该序列为回路。
在图 G1中,V0,V1,V2,V3 是 V0到 V3的路径。
V0,V1,V2,V3,V0是回路。
V0
V4V3
V1
V2
例：
数据结构
tjm
有向图 G2
V0 V1
V2 V3
在图 G2中,V0,V2,V3 是 V0到 V3的路径。
V0,V2,V3,V0是回路。
有向图 G =（ V,{E}）中的顶点序列 v1,v2,…,vk,
若 <vi,vi+1>?E (i=1,2,… k-1),v =v1,u =vk,则
称该序列是从顶点 v到顶点 u的路径。
若 v=u，则称该序列为回路。
例：
数据结构
tjm
在一条路径中,若除起点和终点外,所有顶点各不
相同,则称该路径为简单路径。
由简单路径组成的回路称为简单回路。
在图 G1中,V0,V1,V2,V3 是简单路径。
V0,V1,V2,V4,V1不是简单路径。
在图 G2中,V0,V2,V3,V0是简单回路。
无向图 G1 有向图 G2
V0
V4V3
V1
V2
V0 V1
V2 V3
简单路径和简单回路
数据结构
tjm
非
连
通
图
连
通
图
强
连
通
图
非
强
连
通
图
V0 V1
V2 V3
V0
V4V3
V1
V2
V0 V1
V2 V3
V0
V2V3
V1
V5
V4
连通图（强连通图）
在无（有）向图 G=( V,{E} )中，若对任何两个顶
点 v,u 都存在从 v 到 u 的路径，则称 G是连通图
（强连通图）。
数据结构
tjm
(a) (b) (c)
V0
V4V3
V1
V2
V0
V4V3
V1
V2
V0
V4V3
V1
V2
子图
设有两个图 G=（ V,{E}）,G1=（ V1,{E1}），
若 V1? V,E1 ? E，则称 G1是 G的子图。
例,(b),(c) 是 (a) 的子图
权
某些图的边具有与它相关的数,称之为权。
这种带权图叫做网络。
数据结构
tjm
连通分量（强连通分量）
非
连
通
图
V0
V2V3
V1
V5
V4
无向图 G 的极大连通子图称为 G的连通分量。
极大连通子图意思是：该子图是 G 连通子图，将 G
的任何不在该子图中的顶点加入，子图不再连通。
V0
V2V3
V1
V5
V4
连通分量
数据结构
tjm
有向图 G 的极大强连通子图称为 G的强连通分量。
极大强连通子图意思是：该子图是 G的强连通子图
，将 D的任何不在该子图中的顶点加入，子图不再
是强连通的。 强连通分量
V0 V1
V2 V3
V0
V2 V3
V1
权与网
图中边或弧所具有的相关数称为权。表明从
一个顶点到另一个顶点的距离或耗费。 带权
的图称为 网 。
数据结构
tjm
极小连通子图,该子图是 G 的连通子图，在该子
图中删除任何一条边，子图不再连通。
包含无向图 G 所有顶点的极小连通子图称为 G 的
生成树。对非连通图，则称由各个连通分量的生
成树的集合为非连通图的生成森林。
连通图 G1 G1的生成树
V0
V4V3
V1
V2
V0
V4V3
V1
V2
V0
V4
V3 V1
V2
生成树和生成森林
图的几种基本操作参见 P158。
数据结构
tjm
?
?
? ???
?
，其它
或若
0
Ev,v)v,(v1,
],[ jijijiA
例：
G1
2
4
1
3
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110?
?
?
?
????
7.2.1 数组表示法
邻接矩阵,表示顶点间相联关系的矩阵。
定义：设 G=(V,{E})是有 n?1个顶点的图,G的邻接
矩阵 A是具有以下性质的 n阶方阵,
数据结构
tjm
例,1
5
3
2
4 G2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
???? ?
?
?
?
?
?
?
?
?
?
???
?
，其它
或若 Ev,v)v,(v,
],[ jijiijjiA
?
网的邻接矩
阵可定义为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
6183
624
127
845
375
???? ?
?
?
?
?
?
例,1
4
5
2
3
7
5
3
1
8
6
4
2
数据结构
tjm
邻接矩阵类型定义,
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN} GraphKind;
typedef struct ArcCell
{ VRType adj;
InfoType * info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
typedef struct
{ VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
数据结构
tjm
adjvex nextarc
vexdata firstarc
邻接表的类型定义参见 P163。
7.2.2 邻接表
实现：为图中每个顶点建立一个单链表，第 i个单
链表中的结点表示依附于顶点 Vi的边（有向图中指
以 Vi为尾的弧）。
例：
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
3 2
4
1
^
^
^
^
adjvex nextarc
数据结构
tjm
例,a
e
c
b
d G2
1
2
3
4
a
c
d
b
vexdata firstarc
4
2
1
2 ^
^
^
adjvexnextarc
5 e
4
3 5 ^1
5
3
2 3 ^
数据结构
tjm
例：
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
4
1 ^
1 ^
^
3 ^
adjvex nextarc
逆邻接表：有向图中对每个结点建立以 Vi为弧头
的弧的单链表。
