1
数据结构课程的内容
多对多
（ m:n)
2
8.1
8.1
图的基本概念
图的基本概念
8.2
8.2
图的存储结构
图的存储结构
8.3
8.3
图的遍历
图的遍历
8.4
8.4
图的其它运算
图的其它运算
8.5
8.5
图的应用
图的应用
第
第
8
8
章 图
章 图
3
8.1
8.1
图的基本术语
图的基本术语
其中：
V
是
G
的顶点集合，是有穷非空集；
E
是
G
的边集合，是有穷集。
问：当 E(G) 为空时，图 G 存在否？
答：还存在！但此时图 G 只有顶点而没有边。
有向图：
无向图：
完全图：
图 G 中的每条边都是有方向的；
图 G 中的每条边都是无方向的；
图 G 任意两个顶点都有一条边相连接；
若 n 个顶点的无向图有 n(n-1)/2 条边 , 称为无向完
全图
若 n 个顶点的有向图有 n(n-1) 条边 , 称为有向完全图
V=vertex
E=edge
图：记为 G ＝ ( V, E )
？
v1
v2
v3
v5
v4v4
v1
v2
v3 v4
4
例：判断下列 4 种图形各属什么类型？
无向 无向图
( 树 )
有向图 有向
n
n
(
(
n
n
-1)/2
-1)/2
条边
条边
n
n
(
(
n
n
-1)
-1)
条边
条边
G1 的顶点集合为 V(G1)={0,1,2,3}
边集合为 E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
完全图
完全图
5
稀疏图：
稠密图：
设有两个图 G ＝ (V, E) 和 G’ ＝ (V’, E’) 。若 V’
V 且 E’ E, 则称 图 G’ 是 图 G 的子图。
子 图：
边较少的图。通常边数远少于
nlogn
nlogn
边很多的图。
无向图中，边数接近
n
n
(
(
n
n
-1)/2
-1)/2
有向图中，边数接近
n
n
(
(
n
n
-1)
-1)
