2001 -- 12 -- 27/29
华中科技大学计算机学院 (9)数据结构第七章 图 (Graph)
7.1 图的定义和术语
● 图图 G由顶点集 V和关系集 E组成,记为
G=(V,E)
V是顶点 (元素 )的有穷非空集，
E是两个顶点之间的关系的集合。
A B
C E
D
● 若顶点 a,c之间的关系为 有序对 <a,c>,<a,c>∈E,
则称 <a,c>为从 a到 c的一条 弧 /有向边 ；
a是 <a,c>的 弧尾,
c是 <a,c>的 弧头 ；
G是 有向图 。
例 G1={V1,E1},V1={A,B,C,D,E}
E1={<A,C>,<A,D>,<C,D>,<B,E>,<E,B>}
G1
1 2
5 6
3
G2
● 若顶点 a,b之间的关系为无序对 (a,b),
则称 (a,b)为 无向边 (边）,G是 无向图 。
无向图可简称为图。
(a,b)依附 于 a和 b,(a,b)与 a和 b相关联例 G2={V2,E2},
V2={1,2,3,4,5,6},
E2={(1,3),(1,5),(3,5),(4,6)}
4
v1 A
v2 Cv3
G1 G2 G3 G4 G5
Bv1 v1
v2 D
A
C
B
D
E
● 完全图 ----有 n个顶点和 n(n-1)/2条边的无向图
e=1(1-1)/2
=0
e=2(2-1)/2
=1
e=3(3-1)/2
=3
e=4(4-1)/2
=6
e=5(5-1)/2
=10
● 有向完全图 ----有 n个顶点和 n(n-1)条弧的有向图。
● 网 (Network)----边 (弧 )上加 权 (weight)的图。
1
2 3
G1 G2 G3
1 1
2
1
2 3
无向网 G1
4
A
B C
4
15
5
9 9
4
3
有向网 G2
e=1(1-1)
=0
e=2(2-1)
=2
e=3(3-1)
=6
● 对图 G=(V,E)和 G'=(V',E')，
若 V'?V 且 E'?E,则称 G'是 G的一个 子图
1
2 3
G
4
1
2
G1
3 4
1
G2
3 4
1
G4
1
2 3
G3
4
G1,G2,G3是 G的子图 G4不是 G的子图
2
● 与顶点 x相关联的边 (x,y)的数目,
称为 x的 度,记作 TD(x) 或 D(x)，
TD(1)=1
TD(2)=3
TD(3)=0
● 以顶点 x为弧尾的弧 <x,y>的数目,
称为 x的 出度,记作 OD(x)。
OD(A)=1
OD(B)=2
OD(C)=0
● 以顶点 x为弧头的弧 <y,x>的数目,
称为 x的 入度,记作 ID(x)。
ID(A)=1
ID(B)=1
ID(C)=1
TD(A)=OD(A)+ID(A)=2
TD(B)=OD(B)+ID(B)=3
A
B C
G2
2
5 4
1 3
G1
对无向图 G：
● 若从顶点 vi到 vj有路径,则称 vi和 vj是 连通 的。
● 若图 G中任意两顶点是连通的,则称 G是 连通图 。
1
2 3 4
5 6
A
F E C
B
G
G
D
A
F E C
B
G1
D
G2 G3
● 若图 G'是 G的一个 极大 连通 子图,则称 G'是 G的一个 连通分量 。
G G
G有三个连通分量对有向图 G
● 若在图 G中,每对顶点 vi和 vj之间,从 vi到 vj,且从 vj
到 vi都存在路径,则称 G是 强连通图 。
● 若图 G'是 G的一个 极大强连通子图,则称 G'是 G的一个强连通分量 。 (强连通图的强连通分量是自身 )
B C
G1
A D
B C
G11
是 G1的 强连通分量
A D
B C
G12
不是 G1的 强连通分量
A D
B C
G2
A D
B
C
G21
A D
G22
G2有两个强连通分量
● 设 G=(V,E),G'=(V',E'),V=V',若 G是连通图,
G'是 G的一个 极小 连通 子图,则 G'是 G的一棵 生成树 。
E D
G
B CA
E D
T1
B CA
E D
T4
B CA
E D
T3
B CA
E D
T2
B CA
G的多棵生成树
● 若有向图 G有且仅有一个顶点的入度为 0，其余顶点的入度为 1,则 G是一棵 有向树 。
E D
T1
B CA
E D
T2
B CA
E
B
T3
A
C
E E D
T4
B
CA
E D
T5
B CA
E D
T6
B CA
T1,T2,T3,T4是 有向树 T5,T6不是 有向树
● 有向图的生成树 /生成森林。
E D
G
B CA
E
B
F2
A D
F
F C
E D
T1
B CA
F
E D
F1
B CA
F
E
A
T2
B
F
D
C？
？
E
B
T3
A D
F C
● 图的操作
● 生成 /消除一个图
● 加入一个顶点 /边 (弧 )
● 遍历图
● 求生成树
......
7.2 图的存储结构
7.2.1 数组表示法 /邻接矩阵顶点数组 ---用 一维 数组存储顶点 (元素 )
邻接矩阵 ---用二维数组存储顶点 (元素 )之间的关系 (边或弧 )
1
4 3
G
2 1 2 3 41 0 0 1 1
2 0 0 0 0
3 1 0 0 1
4 1 0 1 0
M=
例 1
邻接矩阵
1 2 3 4
1 2 3 4
顶点数组
V[1..4]
例 2
A
DC
G
B
A B C D
A 0 0 1 1
B 0 0 0 0
C 1 0 0 1
D 1 0 1 0
M=
邻接矩阵
A B C D
1 2 3 4
顶点数组
V[1..4]
顶点 vi的 TD(vi)=M中第 i行 元素之和
n
= ∑ M[i][j]
j=1
顶点 vi的 TD(vi)=M中第 i列 元素之和
n
= ∑ M[j][i]
j=1
例 3
3
1 2
1 2 3
1 0 0 1
2 1 0 0
3 1 1 0
M=
邻接矩阵顶点 vi的 ID(vi)=M中第 i列 元素之和
n
= ∑ M[j][i]
j=1
顶点 vi的 OD(vi)=M中第 i行 元素之和
n
= ∑ M[i][j]
j=1
例 4
1
32
网 G
4
6
5
4 5
8
10
7
14
1 2 3 4 5 6
1 ∞ 4 5 ∞ ∞ ∞
2 4 ∞ 8 ∞ ∞ ∞
3 5 8 ∞ ∞ 10 7
4 ∞ ∞ ∞ ∞ ∞ ∞
5 ∞ ∞ 10 ∞ ∞ 14
6 ∞ ∞ 7 ∞ 14 ∞
思考题：
1.如何求每个顶点的度 D(vi)? 1≤ i≤ n
2.如何求每个顶点的出度 OD(vi)? 1≤ i≤ n
3.如何求每个顶点的入度 ID(vi)? 1≤ i≤ n
M=
邻接矩阵
7.2.2 邻接表,逆邻接表 ----- 链式存储结构。
● 无向图的 邻接表 ----
为 图 G的 每个顶点建立一个单链表，第 i个单链表中的结点表示依附于顶点 vi的边。
若无向图 G有 n个顶点和 e条边，则 G的邻接表需 n个 表 头结点和 2e个表结点。
无向图 G的邻接表，顶点 vi的度为第 i个单链表的 长度。
v4
v5 v6
v3v1
v2
v1
v2
v3 ∧
v4
v5
v6
4
1
2
3
4
5
6
2 ∧
6 ∧
4 5 ∧
5 6 ∧
1 ∧
图 G
图 G邻接表序号 头结点 数组 表 结点 单链表
● 有向图的 邻接表 -----第 i个单链表中的表结点,表示以顶点 vi为尾的弧 (vi,vj)的 弧头。
若有向图 G有 n个顶点和 e条弧，则 G的邻接表需 n个 表 头结点和 e个表结点。
有 向图 G的邻接表，顶点 vi的 出 度为第 i个 单 链表的 长度。
C
E F
BA
D
A
B ∧
C
D
E
F ∧
1
2
3
4
5
6
4 ∧
6 ∧
2 ∧
有向图 G
图 G的 邻接表
2 6 ∧
2
序号 头结点 数组 表 结点 单链表
5
● 有向图的 逆邻接表 -----第 i个单链表中的表结点,表示以顶点 vi为 头 的弧 (vi,vj)的 弧头。
若有向图 G有 n个顶点 e条弧，则 G的逆邻接表需 n个 表 头结点和 e个表结点。
有 向图 G的逆邻接表，顶点 vi的 入 度为第 i个 单 链表的 长度。
C
E F
BA
D
A ∧
B
C ∧
D
E
F
1
2
3
4
5
6 5 ∧
3 ∧
序号 头结点数组 表 结点单链表
1 ∧
有向图 G
图 G的 逆 邻接表
1 3 4 ∧
3
● 有向图的 十字链表 ---
将 邻接表和逆邻接表合并而成的链接表 。 C
BA
D
A
B
C
D
1
2
3
4 1 ∧
G
G的 逆 邻接表
1 3 4 ∧
A
B ∧
C
D
1
2
3
4
4 ∧
3 ∧
G的 邻接表
2 ∧
2
A
B ∧
C
D
1
2
3
4
G的 十字链表
3 2 ∧
1 2
4 2 ∧
1
4 ∧
4 3 ∧ ∧
2
4 ∧
4 1 ∧
1 4 ∧ ∧
7.2.4 邻接多重表 ----（无向图的） 另一种链式存储结构
E
C
BA
D
G
A
B
C
D
E
0 1 2
0 3 2
0 1 4 ∧ ∧
0 3 4 ∧
0 3 5 ∧ ∧0 5 2 ∧
序号 data firstedge
ma vi vj vil vjl
1
2
3
4
5
ma vi vj vil vjl
7.2.4 邻接多重表 ---- （无向图的） 另一种链式存储结构（续）
E
D F
BA
C
G
A
B
C
D
E
F
0 1 2
0 2 3
0 1 3 ∧
0 2 4 ∧
0 3 4 ∧ ∧
0 5 6 ∧ ∧
序号 data firstedge
(A,B)
(A,C)
(B,C)
(B,D)
(C,D)
(E,F)隐含的链接表：
● A (1,2) (1,3)
● B (1,2) (2,3) (2,4)
● C (1,3) (2,3) (3,4)
● D (2,4) (3,4)
● E (5,6)
● F (5,6)
ma vi vj vil vjl
1
2
3
4
5
6
● 图的 一 条 边 或弧 用一个,头结点,表示,其中,
mark----标志域，可用以标记该条边是否被搜索过；
vi和 vj----该条边依附的两个顶点在图中的位置；
vilink----指向下一条依附于顶点 vi的 边；
vjlink----指向下一条依附于顶点 vj的边。
0 1 2
mark vi vj vilink vjlink
data firstedge
A
表示顶点 A的 头结点表示边 或弧 (v1,v2)的 表 结点
● 图的 一个顶点用一个,头结点,表示,其中,
data域 存储和该顶点相关的信息，
firstedge域 存储第一条依附于该顶点的边。
表 结点
华中科技大学计算机学院 (9)数据结构第七章 图 (Graph)
7.1 图的定义和术语
● 图图 G由顶点集 V和关系集 E组成,记为
G=(V,E)
V是顶点 (元素 )的有穷非空集，
E是两个顶点之间的关系的集合。
A B
C E
D
● 若顶点 a,c之间的关系为 有序对 <a,c>,<a,c>∈E,
则称 <a,c>为从 a到 c的一条 弧 /有向边 ；
a是 <a,c>的 弧尾,
c是 <a,c>的 弧头 ；
G是 有向图 。
例 G1={V1,E1},V1={A,B,C,D,E}
E1={<A,C>,<A,D>,<C,D>,<B,E>,<E,B>}
G1
1 2
5 6
3
G2
● 若顶点 a,b之间的关系为无序对 (a,b),
则称 (a,b)为 无向边 (边）,G是 无向图 。
无向图可简称为图。
(a,b)依附 于 a和 b,(a,b)与 a和 b相关联例 G2={V2,E2},
V2={1,2,3,4,5,6},
E2={(1,3),(1,5),(3,5),(4,6)}
4
v1 A
v2 Cv3
G1 G2 G3 G4 G5
Bv1 v1
v2 D
A
C
B
D
E
● 完全图 ----有 n个顶点和 n(n-1)/2条边的无向图
e=1(1-1)/2
=0
e=2(2-1)/2
=1
e=3(3-1)/2
=3
e=4(4-1)/2
=6
e=5(5-1)/2
=10
● 有向完全图 ----有 n个顶点和 n(n-1)条弧的有向图。
● 网 (Network)----边 (弧 )上加 权 (weight)的图。
1
2 3
G1 G2 G3
1 1
2
1
2 3
无向网 G1
4
A
B C
4
15
5
9 9
4
3
有向网 G2
e=1(1-1)
=0
e=2(2-1)
=2
e=3(3-1)
=6
● 对图 G=(V,E)和 G'=(V',E')，
若 V'?V 且 E'?E,则称 G'是 G的一个 子图
1
2 3
G
4
1
2
G1
3 4
1
G2
3 4
1
G4
1
2 3
G3
4
G1,G2,G3是 G的子图 G4不是 G的子图
2
● 与顶点 x相关联的边 (x,y)的数目,
称为 x的 度,记作 TD(x) 或 D(x)，
TD(1)=1
TD(2)=3
TD(3)=0
● 以顶点 x为弧尾的弧 <x,y>的数目,
称为 x的 出度,记作 OD(x)。
OD(A)=1
OD(B)=2
OD(C)=0
● 以顶点 x为弧头的弧 <y,x>的数目,
称为 x的 入度,记作 ID(x)。
ID(A)=1
ID(B)=1
ID(C)=1
TD(A)=OD(A)+ID(A)=2
TD(B)=OD(B)+ID(B)=3
A
B C
G2
2
5 4
1 3
G1
对无向图 G：
● 若从顶点 vi到 vj有路径,则称 vi和 vj是 连通 的。
● 若图 G中任意两顶点是连通的,则称 G是 连通图 。
1
2 3 4
5 6
A
F E C
B
G
G
D
A
F E C
B
G1
D
G2 G3
● 若图 G'是 G的一个 极大 连通 子图,则称 G'是 G的一个 连通分量 。
G G
G有三个连通分量对有向图 G
● 若在图 G中,每对顶点 vi和 vj之间,从 vi到 vj,且从 vj
到 vi都存在路径,则称 G是 强连通图 。
● 若图 G'是 G的一个 极大强连通子图,则称 G'是 G的一个强连通分量 。 (强连通图的强连通分量是自身 )
B C
G1
A D
B C
G11
是 G1的 强连通分量
A D
B C
G12
不是 G1的 强连通分量
A D
B C
G2
A D
B
C
G21
A D
G22
G2有两个强连通分量
● 设 G=(V,E),G'=(V',E'),V=V',若 G是连通图,
G'是 G的一个 极小 连通 子图,则 G'是 G的一棵 生成树 。
E D
G
B CA
E D
T1
B CA
E D
T4
B CA
E D
T3
B CA
E D
T2
B CA
G的多棵生成树
● 若有向图 G有且仅有一个顶点的入度为 0，其余顶点的入度为 1,则 G是一棵 有向树 。
E D
T1
B CA
E D
T2
B CA
E
B
T3
A
C
E E D
T4
B
CA
E D
T5
B CA
E D
T6
B CA
T1,T2,T3,T4是 有向树 T5,T6不是 有向树
● 有向图的生成树 /生成森林。
E D
G
B CA
E
B
F2
A D
F
F C
E D
T1
B CA
F
E D
F1
B CA
F
E
A
T2
B
F
D
C？
？
E
B
T3
A D
F C
● 图的操作
● 生成 /消除一个图
● 加入一个顶点 /边 (弧 )
● 遍历图
● 求生成树
......
7.2 图的存储结构
7.2.1 数组表示法 /邻接矩阵顶点数组 ---用 一维 数组存储顶点 (元素 )
邻接矩阵 ---用二维数组存储顶点 (元素 )之间的关系 (边或弧 )
1
4 3
G
2 1 2 3 41 0 0 1 1
2 0 0 0 0
3 1 0 0 1
4 1 0 1 0
M=
例 1
邻接矩阵
1 2 3 4
1 2 3 4
顶点数组
V[1..4]
例 2
A
DC
G
B
A B C D
A 0 0 1 1
B 0 0 0 0
C 1 0 0 1
D 1 0 1 0
M=
邻接矩阵
A B C D
1 2 3 4
顶点数组
V[1..4]
顶点 vi的 TD(vi)=M中第 i行 元素之和
n
= ∑ M[i][j]
j=1
顶点 vi的 TD(vi)=M中第 i列 元素之和
n
= ∑ M[j][i]
j=1
例 3
3
1 2
1 2 3
1 0 0 1
2 1 0 0
3 1 1 0
M=
邻接矩阵顶点 vi的 ID(vi)=M中第 i列 元素之和
n
= ∑ M[j][i]
j=1
顶点 vi的 OD(vi)=M中第 i行 元素之和
n
= ∑ M[i][j]
j=1
例 4
1
32
网 G
4
6
5
4 5
8
10
7
14
1 2 3 4 5 6
1 ∞ 4 5 ∞ ∞ ∞
2 4 ∞ 8 ∞ ∞ ∞
3 5 8 ∞ ∞ 10 7
4 ∞ ∞ ∞ ∞ ∞ ∞
5 ∞ ∞ 10 ∞ ∞ 14
6 ∞ ∞ 7 ∞ 14 ∞
思考题：
1.如何求每个顶点的度 D(vi)? 1≤ i≤ n
2.如何求每个顶点的出度 OD(vi)? 1≤ i≤ n
3.如何求每个顶点的入度 ID(vi)? 1≤ i≤ n
M=
邻接矩阵
7.2.2 邻接表,逆邻接表 ----- 链式存储结构。
● 无向图的 邻接表 ----
为 图 G的 每个顶点建立一个单链表，第 i个单链表中的结点表示依附于顶点 vi的边。
若无向图 G有 n个顶点和 e条边，则 G的邻接表需 n个 表 头结点和 2e个表结点。
无向图 G的邻接表，顶点 vi的度为第 i个单链表的 长度。
v4
v5 v6
v3v1
v2
v1
v2
v3 ∧
v4
v5
v6
4
1
2
3
4
5
6
2 ∧
6 ∧
4 5 ∧
5 6 ∧
1 ∧
图 G
图 G邻接表序号 头结点 数组 表 结点 单链表
● 有向图的 邻接表 -----第 i个单链表中的表结点,表示以顶点 vi为尾的弧 (vi,vj)的 弧头。
若有向图 G有 n个顶点和 e条弧，则 G的邻接表需 n个 表 头结点和 e个表结点。
有 向图 G的邻接表，顶点 vi的 出 度为第 i个 单 链表的 长度。
C
E F
BA
D
A
B ∧
C
D
E
F ∧
1
2
3
4
5
6
4 ∧
6 ∧
2 ∧
有向图 G
图 G的 邻接表
2 6 ∧
2
序号 头结点 数组 表 结点 单链表
5
● 有向图的 逆邻接表 -----第 i个单链表中的表结点,表示以顶点 vi为 头 的弧 (vi,vj)的 弧头。
若有向图 G有 n个顶点 e条弧，则 G的逆邻接表需 n个 表 头结点和 e个表结点。
有 向图 G的逆邻接表，顶点 vi的 入 度为第 i个 单 链表的 长度。
C
E F
BA
D
A ∧
B
C ∧
D
E
F
1
2
3
4
5
6 5 ∧
3 ∧
序号 头结点数组 表 结点单链表
1 ∧
有向图 G
图 G的 逆 邻接表
1 3 4 ∧
3
● 有向图的 十字链表 ---
将 邻接表和逆邻接表合并而成的链接表 。 C
BA
D
A
B
C
D
1
2
3
4 1 ∧
G
G的 逆 邻接表
1 3 4 ∧
A
B ∧
C
D
1
2
3
4
4 ∧
3 ∧
G的 邻接表
2 ∧
2
A
B ∧
C
D
1
2
3
4
G的 十字链表
3 2 ∧
1 2
4 2 ∧
1
4 ∧
4 3 ∧ ∧
2
4 ∧
4 1 ∧
1 4 ∧ ∧
7.2.4 邻接多重表 ----（无向图的） 另一种链式存储结构
E
C
BA
D
G
A
B
C
D
E
0 1 2
0 3 2
0 1 4 ∧ ∧
0 3 4 ∧
0 3 5 ∧ ∧0 5 2 ∧
序号 data firstedge
ma vi vj vil vjl
1
2
3
4
5
ma vi vj vil vjl
7.2.4 邻接多重表 ---- （无向图的） 另一种链式存储结构（续）
E
D F
BA
C
G
A
B
C
D
E
F
0 1 2
0 2 3
0 1 3 ∧
0 2 4 ∧
0 3 4 ∧ ∧
0 5 6 ∧ ∧
序号 data firstedge
(A,B)
(A,C)
(B,C)
(B,D)
(C,D)
(E,F)隐含的链接表：
● A (1,2) (1,3)
● B (1,2) (2,3) (2,4)
● C (1,3) (2,3) (3,4)
● D (2,4) (3,4)
● E (5,6)
● F (5,6)
ma vi vj vil vjl
1
2
3
4
5
6
● 图的 一 条 边 或弧 用一个,头结点,表示,其中,
mark----标志域，可用以标记该条边是否被搜索过；
vi和 vj----该条边依附的两个顶点在图中的位置；
vilink----指向下一条依附于顶点 vi的 边；
vjlink----指向下一条依附于顶点 vj的边。
0 1 2
mark vi vj vilink vjlink
data firstedge
A
表示顶点 A的 头结点表示边 或弧 (v1,v2)的 表 结点
● 图的 一个顶点用一个,头结点,表示,其中,
data域 存储和该顶点相关的信息，
firstedge域 存储第一条依附于该顶点的边。
表 结点
