第7章 图
CAC - 2
CAC - 3
7.1 图的定义和术语
7.1.1 图的定义和术语
1. 图的定义（graph）
图G由两个集合构成，记作G=<V,E> ，其中V是顶点的非空有限集合，
E是顶点间关系----边的有限集合，边是顶点的无序对或有序对集合。 。
【例】 V0
V1
V2
V3
V4
无序对(vi,vj)： 用连接顶点vi、vj的线段
V0
V1
V0
V1
V2
V3
V2
V3
两个强连通分量
CAC - 17
练习
具有n个顶点的强连通图至少有多少条边？是什么形状？
分析：强连通图是针对有向图而言的。由于强连通图要求 图中任何2个顶点之间能够连通，因此每个顶点至少要有一条 以该顶点为终点（弧头）和出发点（弧尾）的弧，每个顶点 的入度和出度至少各为1，即顶点的度至少为2。
边或弧
G2=<V2,E2> V2={ v0 ,v1,v2,v3 } E2={ <v0,v1 > , <v0,v2 >, <v2,v3 >,<v3,v0 > }
CAC - 6
7.1.1 图的定义和术语
2. 图的相关术语 （1）无向图：若图G中所有边是没有方向的，则称G为无向图。 （2）有向图：若图G中所有顶点间的连线是有方向的，则称G为有向图。 （3）顶点：数据元素Vi称为顶点。 （4）边和弧：P(Vi,Vj)表示在顶点Vi和Vj之间有线相连，如果是无向图， 则称该线为边；在有向图中，则称该连线为弧。边用顶点的无序偶对(Vi， Vj)表示，弧用有序偶对< Vi，Vj >表示。 （5）弧头和弧尾：有序偶对的第一个结点称为始点（或弧尾，即不带箭 头的一端），有序偶对的第二个结点称为终点（或弧头，即带箭头的一 端）。
（12）路径长度：非带权图的路径长度是指此路径上边的条数，带权图的 路径长度是指路径上各边的权之和。
V0
V1
V2
V3
V4
V0
V1
V2
V3
CAC - 11
7.1.1 图的定义和术语
（13）回路：若路径上第一个顶点 V1 与最后一个顶点Vm 重合，则称这样 的路径为回路或环。
（14）简单路径：若路径上各顶点 V1,V2,...,Vm 均不互相重复，则称这样 的路径为简单路径。
表示，称为无向边；
G1=<V1,E1>
V1={v0,v1,v2,v3,v4 } E1={ (v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3) ,(v2,v4) }
CAC - 5
7.1.1 图的定义和术语
V0
V1
V2
V3
有序对<vi,vj> ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向
（6）有向完全图：在有向图中，如果任意两个顶点间都有方向互为相反 的两条弧连接，则称该图为有向完全图。n个顶点的有向图最大边数是 n(n-1)。 （7）无向完全图：在无向图中，如果任意两个顶点间都有一条边连接， 则称该图为无向完全图。n个顶点的无向图最大边数是n(n-1)/2。
（8）稠密图、稀疏图：若一个图接近完全图，则称为稠密图；边数很少 的图称为稀疏图。
顶点V的入度(ID)：以V为终点有向边数
顶点V的度TD(V)= OD(V)+ID(V)
V2
V3
CAC - 10
7.1.1 图的定义和术语
（10）边的权、网：与图的边或弧相关的数据信息称为权。在实际应用中， 权值可以有某种含义。边上带权的图称为网。
（11）路径：在图G=(V,E )中, 若从顶点Vi出发,沿一些边经过一些顶点Vp1, Vp2, …, Vpm，到达顶点Vj。则称顶点序列 (Vi,Vp1,Vp2 ... Vpm,Vj )为从顶点 Vi 到顶点Vj 的路径。它经过的边(Vi,Vp1)、(Vp1,Vp2)、...、(Vpm ,Vj)应是属 于E 的边。
（15）简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出 现的回路叫简单回路。
CAC - 12
7.1.1 图的定义和术语
(16) 子图
设有两个图 G＝(V, E) 和 G’＝(V’, E ’)。若 V’ V 且 E ’ E, 则称 图G’ 是 图G 的子图。
V0
V1
V2
V3
V4
(a)
V0
V1
V2
V3
V4
(b)
V0
V2
V3
V4
(c)
CAC - 13
7.1.1 图的定义和术语
(17) 连通、连通图：从顶点V 到顶点W 有一条路径，则说V和 W是连通的。图中任意两个顶点都是连通的图叫连通图。
V0
V1
V2
V3
V4
V0
V1
V4
V3
V2
V5
CAC - 14
7.1.1 图的定义和术语
（18）连通分量：无向图G的极大连通子图称为G的连通分量。 “极大”的含义是：该子图是G连通子图，将G的任何不在 该子图中的顶点加入，子图不再连通。
非
V0
V1
V4
连
通
图
V3
V2
V5
两个连通分量
CAC - 15
7.1.1 图的定义和术语
（19）强连通图：有向图中，如果对每一对顶点Vi，VjV, ViVj，从Vi到Vj 和从Vj到 Vi 都存在路径，则称G是强连通 图。
V0
V1
V0
V1
V2
V3Biblioteka V2V3CAC - 16
7.1.1 图的定义和术语
（20）强连通分量：有向图的极大强连通子图称为强连通分 量。
CAC - 7
7.1.1 图的定义和术语
描述图中两种关系的术语 ➢ 邻接：顶点之间的关系。若Vi与Vj间有边相连接， 则Vi与Vj互称邻接点； ➢ 关联：边与顶点间的关系。若Vi与Vj间有边相连接， 则称边(Vi,Vj)关联于顶点Vi,Vj。
V0
V1
V2
V3
V4
CAC - 8
7.1.1 图的定义和术语
CAC - 9
7.1.1 图的定义和术语
（9）顶点的度、入度、出度： 顶点V的度：关联于某顶点V 的边的数目。
V0
V1
V2
V3
V4
顶点的度与边数之间的关系：设图G的 顶点数为n，边数为e，则图的所有顶点 的度数和为2*e（每条边对图的所有顶 点的度数和“贡献”2度）
在有向图中：
V0
V1
顶点V的出度(OD)：以V为起点有向边数
这样根据图的顶点数、边数和各顶点度3者之间的关系， 可得边数=2*n/2=n。
对于强连通图，由于从每个顶点都可以到达其余所有顶点， 因此当每个顶点的入度和出度都为1时，这个图一定是一个n 的顶点构成的环。
CAC - 18
7.1.2 图的基本运算
1. LocateVex(G,u) 初始条件：图G存在 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否 则返回其它信息。 2. GetVex(G,v) 初始条件：图G存在，v是G中某个顶点的编号 操作结果：返回v的值 3. FirstAdjVex(G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接 顶点，则返回“空”。