数据结构 第七章图

两个强连通分量
练 习
具有n个顶点的强连通图至少有多少条边？是什么形状？
分析：强连通图是针对有向图而言的。由于强连通图要求 图中任何2个顶点之间能够连通，因此每个顶点至少要有一条 以该顶点为终点（弧头）和出发点（弧尾）的弧，每个顶点 的入度和出度至少各为1，即顶点的度至少为2。
这样根据图的顶点数、边数和各顶点度3者之间的关系， 可得边数=2*n/2=n。 对于强连通图，由于从每个顶点都可以到达其余所有顶点， 因此当每个顶点的入度和出度都为1时，这个图一定是一个n 的顶点构成的环。
网络的邻接矩阵可定义为：
7.2.1 数组表示法
邻接矩阵表示法类型定义： #define Max_Vertex_Num 100 /*最大顶点个数*/ typedef char VertexType; /*顶点类型*/ typedef int EdgeType; /*设边权值为整型*/ typedef struct {VertexType vexs[Max_Vertex_Num]; /*存储顶点的一维数组*/ EdgeType edges[Max_Vertex_Num][Max_Vertex_Num]; /*存储邻接矩阵的二维数组*/ int n,e; /*图的顶点数和弧数*/ }Mgraph; 用邻接矩阵表示法，图 G占用存储空间与顶点数有关，与边数无关； 适用于边稠密的图。
（8）稠密图、稀疏图：若一个图接近完全图，则称为稠密图；边数很少 的图称为稀疏图。
7.1.1 图的定义和术语
（9）顶点的度、入度、出度：
顶点V的度：关联于某顶点V 的边的数目。
V0 V2 V3 V4 V1
顶点的度与边数之间的关系：设图G的 顶点数为n，边数为e，则图的所有顶点 的度数和为2*e（每条边对图的所有顶 点的度数和“贡献”2度）
/*邻接表*/
/*以邻接表方式存储的图类型*/
用邻接表存储图，图 G占用存储空间与顶点数有关，与边数也有关；
1. 邻接表
（2）无向图的邻接表
0
V0 V2 V3 V4 V1 1 2 顶点表 V0 边表 1 0 1
3
2 3 2 2 4
V1
V2 V3
4
3
4 ……
0
1
V4
5
6
1. 邻接表
（3）无向图的邻接表的特点：邻接表中，同一条边对应两个 边结点。 （4）邻接表的使用 求顶点v的度 判定两顶点v、u是否邻接 在图中增减边
7.2.1 数组表示法
约定顶点的编号 : G=<V, E>是图, V={v0,v1, … vn-1 },设顶点的角标为它的编号。
V0 V2 V1 V0 V1
7 V0 5 V1 8
3
1 V4 4
V3
0 0 1 2 1 2 3
V4
4
V2
0 0 1 1 2
V3
3
6
2 1 2
V2
0 0 0 1 5 2 7 3 0
V0 V2 V3 V4 V3 V2 V5 V1 V0 V1 V4
7.1.1 图的定义和术语
（18）连通分量：无向图G的极大连通子图称为G的连通分量。 “极大”的含义是：该子图是G连通子图，将G的任何不在 该子图中的顶点加入，子图不再连通。 非 连 通 图
V0 V1 V4
V3
V2
V5
两个连通分量
7.1.1 图的定义和术语
7.2 图的存储结构
V0
V1
V0 V2
V1
V2
V3
V3
V4
图的存储结构至少要保存两类信息：
1) 顶点的数据
2) 顶点间的关系
如何表示顶点间的关系
7.2.1 数组表示法
1. 邻接矩阵 —— 表示顶点间邻接关系的矩阵。
定义：设G=(V,E)是有n≥1个顶点的图，G的邻接矩阵A是具有 以下性质的n阶方阵：
3 4
3 8 1 6 0
7.2.1 数组表示法
2. 邻接矩阵特点
（1）有n个顶点的无向图的存储空间可以小于n² 。 邻接矩阵 中，同一条边表示了两次，是对称矩阵，可压缩存储。
（2）有n个顶点的有向图的存储空间为n² 。有向图邻接矩阵 不一定对称。
7.2.1 数组表示法
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中没有邻接 顶点，则返回“空”。
（19）强连通图：有向图中，如果对每一对顶点Vi，VjV, ViVj，从Vi到Vj 和从Vj到 Vi 都存在路径，则称G是强连通 图。
V0 V1 V0 V1
V2
V3
V2
V3
7.1.1 图的定义和术语
（20）强连通分量：有向图的极大强连通子图称为强连通分 量。
V0 V1 V0 V1 V2 V3 V2 V3
7.1.2 图的基本运算
4. NextAdjVex(G, v, w) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v 的最后一个邻接点，则返回“空”。 5. DFSTraverse(G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：从顶点v起深度优先遍历图G，对每个顶点访问一 次且仅一次 6. BFSTraverse(G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：从顶点v起广度优先遍历图G，对每个顶点访问一 次且一次。
7.1.1 图的定义和术语
（13）回路：若路径上第一个顶点 V1 与最后一个顶点Vm 重合，则称这样 的路径为回路或环。 （14）简单路径：若路径上各顶点 V1,V2,...,Vm 均不互相重复，则称这样 的路径为简单路径。
（15）简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出 现的回路叫简单回路。
7.1.1 图的定义和术语
描述图中两种关系的术语 邻接：顶点之间的关系。若Vi与Vj间有边相连接， 则Vi与Vj互称邻接点； 关联：边与顶点间的关系。若Vi与Vj间有边相连接， 则称边(Vi,Vj)关联于顶点Vi,Vj。
V0 V2 V3 V4 V1
7.1.1 图的定义和术语
（6）有向完全图：在有向图中，如果任意两个顶点间都有方向互为相反 的两条弧连接，则称该图为有向完全图。n个顶点的有向图最大边数是 n(n-1)。 （7）无向完全图：在无向图中，如果任意两个顶点间都有一条边连接， 则称该图为无向完全图。n个顶点的无向图最大边数是n(n-1)/2。
{ int adjvex;
}EdgeNode; 图的定邻接点域*/
/*链域*/
struct node *next;
{VertexNode adjlist [Max_Vertex_Num];
int n,e; }ALGraph; 适用于边稀疏的图。 /*顶点数和边数*/
G2=<V2,E2> V2={ v0 ,v1,v2,v3 } E2={ <v0,v1 > , <v0,v2 >, <v2,v3 >,<v3,v0 > }
7.1.1 图的定义和术语
2. 图的相关术语
（1）无向图：若图G中所有边是没有方向的，则称G为无向图。
（2）有向图：若图G中所有顶点间的连线是有方向的，则称G为有向图。 （3）顶点：数据元素Vi称为顶点。
3
……
操作步骤：建立顶点信 息表，存储顶点数4，边 数4
4 4
顶点数 边数
2. 有向图的邻接表和逆邻接表
【建立有向图邻接表示例】
V0 V1 0 1 2 V2 V3 V0 V1 V2 V3
2
3
……
输入边<0,2>
4 4
顶点数 边数
2. 有向图的邻接表和逆邻接表
V0 V1
在有向图中： 顶点V的出度(OD)：以V为起点有向边数 顶点V的入度(ID)：以V为终点有向边数 顶点V的度TD(V)= OD(V)+ID(V)
V2
V3
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 的边。 （12）路径长度：非带权图的路径长度是指此路径上边的条数，带权图的 路径长度是指路径上各边的权之和。 V0 V2 V3 V4 V2 V3 V1 V0 V1
3. 邻接矩阵的使用
（1）统计顶点的度
无向图：邻接矩阵中第i 行或第i列非0元素的个数 有向图：顶点Vi的出度是矩阵中第i行非0元素个数， 顶点Vi的入度是矩阵中第i列非0元素个数; （2）顶点不变，在图中增加/删除边： 将二维数组对应分量赋值1或清0 （3）判断任意两个顶点之间是否相连 （4）统计图中有多少条边
统计图中有多少条边
2. 有向图的邻接表和逆邻接表
（1）有向图的邻接表 将以同一顶点为起点的弧存储在边表中。
0
V0 V1 1 2 3 V2 V3 …… V0 V1
1 3 0
2
V2
V3
4 4
顶点数 边数
2. 有向图的邻接表和逆邻接表