第 7 章 图

2019/10/19,第七章 图 (Graph),2019/10/19,1、图的基本概念； 2、图的存储结构（邻接矩阵、邻接表、十字邻接表）； 3、图的遍历（深度优先搜索、广度优先搜索）； 4、最小生成树（kruskul算法、prim算法）； 5、最短路径（dijkstra算法、floyd算法）； 6、AOV网络与拓扑排序； 7、AOE网络与关键路径。,教学内容,2019/10/19,图的特点,顶点的前驱和后继个数无限制,图的应用,顶点之间的关系是任意的,图中任意两个顶点之间都可能相关,图（Graph）是一种非线性结构。,计算机科学,多对多,2019/10/19,7.1 图的定义和术语,定义：,图是一种： 数据元素间存在多对多关系的数据结构 加上一组基本操作构成的抽象数据类型。,ADT Graph 数据对象：V是具有相同特性的数据元素的集合， 称为顶点集。 数据关系：R = VR VR= | v, wV 且 P(v, w), 表示从 v 到 w 的弧， 谓词P(v,w)定义了弧 的意义或信息 基本操作：,2019/10/19,基本术语：,有向图,顶点：图中的数据元素。,弧：若 VR，则 表示从 v 到 w 的一条 弧，且称 v 为弧尾，称 w 为弧头，此时的图称为有向图。,G1 = (V1, A1) V1 = v1, v2, v3, v4 A1 = , , , ,2019/10/19,无向图,边：若 VR 必有VR，则以 无序对 (v, w) 代表这两个有序对，表示 v 和 w 之 间的一条边，此时的图称为无向图。,G2 = (V2, E2) V2 = v1, v2, v3, v4, v5 E2 = (v1, v2), (v1, v4), (v2, v3), (v2, v5) , (v3, v4), (v3, v5),2019/10/19,无向图中边的取值范围：0en(n-1)/2。 （用 n 表示图中顶点数目，用 e 表示边的数目。 且不考虑顶点到其自身的边。）,完全图：有 n(n-1)/2 条边的无向图（即： 每两个顶点之间都存在着一条边)称为完全图。,有向完全图：有 n (n - 1) 条弧的有向图 （即：每两个顶点之间都存在着方向相反的 两条弧）称为有向完全图。,有向图中弧的取值范围：0en(n-1)。 （用 n 表示图中顶点数目，用 e 表示弧的数目。 且不考虑顶点到其自身的弧。）,2019/10/19,稀疏图：含有很少条边或弧的图。,稠密图：含有很多条边或弧的接近完全图的图。,权：与图的边或弧相关的数，这些数可以表示从 一个顶点到另一个顶点的距离或耗费。,网： 带权的图。,2019/10/19,子图：如果图 G = (V, E) 和 G´= (V ´, E´)，满足： V ´ V 且 E´ E，则称 G´为G 的子图。,2019/10/19,邻接点：若 (v, v´) 是一条边，则称顶点 v 和 v´互为 邻接点，或称 v 和 v´相邻接；称边 (v, v´) 依附于顶点 v 和 v´，或称 (v, v´) 与顶点 v 和 v´ 相关联。,若 是一条弧，则称顶点 v 邻接到 v´，顶点 v´邻接自顶点 v。并称弧 与顶点 v 和 v´ 相关联。,2019/10/19,度：无向图中顶点 v 的度是和 v 相关联的边的数目，记为： TD(v)。,入度：有向图中以顶点 v 为头的弧的数目称为 v 的入度， 记为：ID(v)。,出度：有向图中以顶点 v 为尾的弧的数目称为 v 的出度， 记为：OD(v)。,度：入度和出度之和，即：TD(v) = ID(v) + OD(v)。,如果顶点 vi 的度为 TD(vi)，则一个有 n 个顶点 e 条 边（弧）的图，满足如下关系：,2019/10/19,路径：从顶点 v 到 v´ 的路径是一个顶点序列 (v = vi, 0, vi, 1, , vi, m= v´)，满足 (vi, j-1, vi, j)VR 或 VR，(1 j m)。,对于有向图，路径也是有向的。,路径长度：路径上边或弧的数目。,回路（环）：第一个顶点和最后一个顶点相同的路径。,2019/10/19,简单路径：序列中顶点（两端点除外）不重复出现的路径。,简单回路（简单环）：前后两端点相同的简单路径。,连通：从顶点 v 到 v´ 有路径，则说 v 和 v´ 是连通的。,连通图：图中任意两个顶点都是连通的。,非连通图：有 n 个顶点和小于 n-1 条边的图。,2019/10/19,连通分量：无向图的极大连通子图（该子图是 G 连通子图，G中再加一个顶点就不连通，再减一条边就不极大）；任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量（非连通图的每一个连通部分）。,强连通图： 任意两个顶点都连通的有向图。,强连通分量：有向图的极大强连通子图（该子图是D强连通子图，G中再加一个顶点就不连通，再减一条边就不极大）；任何强连通图的强连通分量只有一个，即其本身；非强连通图有多个强连通分量。,连通图,非连通图,v2,v1,v3,v4,v5,连通分量,强连通图,两个强连通分量,非强连通图,非连通分量,2019/10/19,（无向图）生成树：包含无向图G 所有顶点的的极小连通子图（该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通；加入一条边，则子图一定有环。 ）。,一个图可以有许多棵不同的生成树。,注,所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同； 生成树是图的极小连通子图； 一个有 n 个顶点的连通图的生成树有 n-1 条边； 生成树中任意两个顶点间的路径是唯一的； 在生成树中再加一条边必然形成回路。,含 n 个顶点 n-1 条边的图不一定是生成树。,2019/10/19,（无向图） 生成森林：由若干棵生成树组成，含有图中 全部顶点，但只有足以构成若干棵不相交的生成树的边。,有向树：如果一个有向图恰有一个顶点的入度为 0 ， 其余顶点的入度均为 1 ，则是一棵有向树。,有向图的生成森林：由若干棵有向树组成，含有图中 全部顶点，但只有足以构成若干棵不相交的有向树的弧。,2019/10/19,7.2 图的存储结构,图的存储结构要保存两类信息： 1)顶点的数据 2)顶点间的关系,顺序存储：任意两顶点都可能有联系，不能用元素在存储区中的物理位 置来表示元素之间的关系。 多重链表：与树类似，浪费存储单元；操作不方便。,？,2019/10/19,7.2.1 数组表示法（邻接矩阵表示法）,一个有 n 个顶点的图，可用两个数组存储。其中一个 一维数组存储数据元素（顶点）的信息，另一个二维数组 （邻接矩阵）存储数据元素之间的关系（边或弧）的信息。,邻接矩阵：设 G = (V, VR) 是具有 n 个顶点的图，顶点 的顺序依次为 v1, v2, , vn，则 G 的邻接矩阵是具有如下 性质的 n 阶方阵：,2019/10/19,v1 v2 v3 v4,v1 v2 v3 v4 v5,v1 v2 v3 v4,v1 v2 v3 v4 v5,特点：,无向图的邻接矩阵对称，可压缩存储；有 n 个顶点的无 向图所需存储空间为 n(n-1)/2。,有 n 个顶点的有向图所需存储空间为n²，用于稀疏图时空 间浪费严重。G占用存储空间只与它的顶点数有关，与边 数无关；适用于边稠密的图；,无向图中顶点 vi 的度 TD(vi) 是邻接矩阵中第 i 行 1 的个数。,有向图中,顶点 vi 的出度是邻接矩阵中第 i 行 1 的个数。,顶点 vi 的入度是邻接矩阵中第 i 列 1 的个数。,2019/10/19,网的邻接矩阵可定义为：,v1 v2 v3 v4 v5 v6,v1 v2 v3 v4 v5 v6,2019/10/19,图的数组（邻接矩阵）存储表示：,#define INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 / 最大顶点个数 typedef enum DG, DN, UDG, UDN GraphKind; /有向图,有向网,无向图,无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;,2019/10/19,7.2.2 邻接表（类似于树的孩子链表表示法）,头结点,表结点,3,1,4,2,0,4,3,1,2,0,2,1,特点：,若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头 结点和 2e 个表结点。适宜存储稀疏图。,无向图中顶点 vi 的度为第 i 个单链表中的结点数。,2019/10/19,0,1,2,3,2,1,3,0,v1,v3,v4,v2,邻接表,逆邻接表,顶点 vi 的出度为第 i 个 单链表中的结点个数。,特点：,顶点 vi 的入度为整个单 链表中邻接点域值是 i-1 的结点个数。,找出度易， 找入度难。,找入度易， 找出度难。,顶点 vi 的入度为第 i 个 单链表中的结点个数。,顶点 vi 的出度为整个单 链表中邻接点域值是 i-1 的结点个数。,2019/10/19,图的邻接表存储表示：,#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph;,2019/10/19,弧结点,7.2.3 十字链表,顶点结点,2019/10/19,#define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex, headvex; / 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType *info; / 该弧相关信息的指针 ArcBox; typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧 VexNode; typedef struct VexNode xlistMAX_VERTE