数据结构(C语言版)第7章图

1、第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题 7.5 7.5 有向无环图及其应用有向无环图及其应用7.67.6最短路径最短路径 1、图的基本概念；、图的基本概念； 2、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）；、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）； 3、图的遍历（深度优先搜索、广度优先搜索）；、图的遍历（深度优先搜索、广度优先搜索）； 4、最小生成树（、最小生成树（kruskul算法、算法、prim算法）；算法）； 5、最短路径（、

2、最短路径（dijkstra算法、算法、floyd算法）；算法）； 6、AOV网络与拓扑排序；网络与拓扑排序； 7、AOE网络与关键路径。网络与关键路径。 教学内容教学内容 图的特点图的特点 顶点的前驱和后继个数无限制顶点的前驱和后继个数无限制 图的应用图的应用顶点之间的关系是任意的顶点之间的关系是任意的 图中任意两个顶点之间都可能相关图中任意两个顶点之间都可能相关 图（图（Graph）是一种）是一种非线性结构非线性结构。 语语 言言 学学逻逻 辑辑 学学物物 理理化化 学学电信工程电信工程 数数 学学 北京北京 西安西安 南京南京 杭州杭州 开封开封 洛阳洛阳 7.1 图的定义和术语图的定义和

3、术语 定义：定义： 图图是一种：是一种： 数据元素间存在多对多关系的数据结构数据元素间存在多对多关系的数据结构 加上一组基本操作构成的加上一组基本操作构成的抽象数据类型抽象数据类型。 ADT Graph 数据对象：数据对象：V 是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。 数据关系：数据关系：R = VR VR = | v, wV 且且 P(v, w), 表示从表示从 v 到到 w 的弧，的弧， 谓词谓词 P(v, w) 定义了弧定义了弧 的意义或信息的意义或信息 基本操作：基本操作： 定义：定义： 图图 (Graph) 是一种复杂的非线性数据结构，

4、由是一种复杂的非线性数据结构，由 顶点集合及顶点间的关系（也称弧或边）集合组成。顶点集合及顶点间的关系（也称弧或边）集合组成。 可以表示为：可以表示为：G(V, VR) 其中其中 V 是是顶点顶点的有穷非空集合；的有穷非空集合； VR 是是顶点之间关系顶点之间关系 的有穷集合，也叫做的有穷集合，也叫做弧弧或或边边集合。弧集合。弧是顶点的有序对，是顶点的有序对， 边是顶点的无序对边是顶点的无序对。 基本操作：基本操作： 结构初始化结构初始化CreateGraph(&G, V, VR);初始条件：初始条件：V 是图的顶点集，是图的顶点集，VR 是图中弧的集合。是图中弧的集合。 操作结果：操

5、作结果：按按 V 和和 VR 的定义构造图的定义构造图 G。 销毁结构销毁结构DestroyGraph(&G);初始条件：初始条件：图图 G 存在。存在。操作结果：操作结果：销毁图销毁图 G。 引用型操作引用型操作LocateVex(G, u);初始条件：初始条件：图图 G 存在，存在，u 和和 G 中顶点有相同特征。中顶点有相同特征。操作结果：操作结果：若若 G 中存在和中存在和 u 相同的顶点，则返回该顶点在图相同的顶点，则返回该顶点在图 中中；否则返回其它信息。；否则返回其它信息。 GetVex(G, v);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点。中某

6、个顶点。 操作结果：操作结果：返回返回 v 的值。的值。 FirstAdjVex(G, v);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：操作结果：返回返回 v 的第一个的第一个。若该顶点在。若该顶点在 G 中没有邻中没有邻 接点，则返回接点，则返回“空空”。 顶点在图中的顶点在图中的“位置位置”指指 的是，在图的存储结构中顶的是，在图的存储结构中顶 点之间自然形成的相对位置。点之间自然形成的相对位置。 若若G，则，则 称称 w 为为 v 的邻接点，的邻接点， 若若(v,w)G，则称，则称 w 和和 v 互为邻接点。互为邻接点。 NextAdjVe

7、x(G, v, w);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点，中某个顶点，w 是是 v 的邻接顶点。的邻接顶点。 操作结果：操作结果：返回返回 v 的（相对于的（相对于 w 的）的）邻接点。若邻接点。若 w 是是 v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。 若若 v 有多个邻有多个邻接接 点，则在图的存储点，则在图的存储结结 构建立之后，其邻构建立之后，其邻接接 点之间的相对次序点之间的相对次序也也 就自然形成了。就自然形成了。 加工型操作加工型操作PutVex(&G, v, value);初始条件：初始条件：图图 G 存在，存在，v 是

8、是 G 中某个顶点。中某个顶点。 操作结果：操作结果：对对 v 赋值赋值 value。 InsertVex(&G, v);初始条件：初始条件：图图 G 存在，存在，v 和图中顶点有相同特征。和图中顶点有相同特征。 操作结果：操作结果：在图在图 G 中增添新顶点中增添新顶点 v。 DeleteVex(&G, v);初始条件：初始条件：图图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。 操作结果：操作结果：删除删除 G 中顶点中顶点 v 及其相关的弧。及其相关的弧。 InsertArc(&G, v, w);初始条件：初始条件：图图 G 存在，存在，v 和和 w 是

9、是 G 中两个顶点。中两个顶点。操作结果：操作结果：在在 G 中增添弧中增添弧 ，若，若 G 是无向的，则还增添是无向的，则还增添 对称弧对称弧 。 DeleteArc(&G, v, w);初始条件：初始条件：图图 G 存在，存在，v 和和 w 是是 G 中两个顶点。中两个顶点。操作结果：操作结果：在在 G 中删除弧中删除弧 ，若，若 G 是无向的，则还删除是无向的，则还删除 对称弧对称弧 。 DFSTraverse(G, Visit();初始条件：初始条件：图图 G 存在，存在，Visit 是顶点的访问函数。是顶点的访问函数。操作结果：操作结果：对图对图 G 进行进行深度优先遍历深度

10、优先遍历。遍历过程中对每个顶。遍历过程中对每个顶 点调用函数点调用函数 Visit 一次且仅一次。一旦一次且仅一次。一旦 visit() 失败，失败， 则操作失败。则操作失败。 BFSTraverse(G, Visit();初始条件：初始条件：图图 G 存在，存在，Visit 是顶点的访问函数。是顶点的访问函数。操作结果：操作结果：对图对图 G 进行进行广度优先遍历广度优先遍历。遍历过程中对每个顶。遍历过程中对每个顶 点调用函数点调用函数 Visit 一次且仅一次。一旦一次且仅一次。一旦 visit() 失败，失败， 则操作失败。则操作失败。 ADT Graph 基本术语：基本术语： 有向图有

11、向图 无向图无向图 图中的数据元素。图中的数据元素。 v2 v1 v3 v4 G1 v2 v1 v3 v4 v5 G2 若若 VR，则，则 表示从表示从 v 到到 w 的的 一条弧，且称一条弧，且称 v 为为，称，称 w 为为， 此时的图称此时的图称 为为。 G1 = (V1, A1) V1 = v1, v2, v3, v4 A1 = , , , 若若 VR 必有必有VR，则以无序，则以无序 对对 (v, w) 代表这两个有序对，表示代表这两个有序对，表示 v 和和 w 之间的一条之间的一条 边，此时的图称为边，此时的图称为。 G2 = (V2, E2) V2 = v1, v2, v3, v4

12、, v5 E2 = (v1, v2), (v1, v4), (v2, v3), (v2, v5) , (v3, v4), (v3, v5) 例：例：两个城市两个城市 A 和和 B ，如果，如果 A 和和 B 之间的连线的涵义是表示两之间的连线的涵义是表示两 个城市的距离，则个城市的距离，则 和和 是相同的，用是相同的，用 (A, B) 表示。表示。 如果如果 A 和和 B 之间的连线的涵义是表示两城市之间人口流动之间的连线的涵义是表示两城市之间人口流动 的情况，则的情况，则 和和 是不同的。是不同的。 北北 京京 上上 海海 北北 京京 上上 海海 (北京，上海北京，上海) 无向图中边的取值范

13、围：无向图中边的取值范围：0en(n-1)/2。（用（用 n 表示图中顶点数目，用表示图中顶点数目，用 e 表示边的数目。且不表示边的数目。且不 考虑顶点到其自身的边。）考虑顶点到其自身的边。） 有有 n(n-1)/2 条边的无向图（即：无向图条边的无向图（即：无向图 中每两个顶点之间都存在着一条边中每两个顶点之间都存在着一条边) )称为称为。 有有 n(n-1) 条弧的有向图（即：有向条弧的有向图（即：有向 图中每两个顶点之间都存在着方向相反的两条弧）称图中每两个顶点之间都存在着方向相反的两条弧）称 为为。v2 v1 v3 v4 v5 有向图中弧的取值范围：有向图中弧的取值范围：0en(n-

14、1)。（用（用 n 表示图中顶点数目，用表示图中顶点数目，用 e 表示弧的数目。且不表示弧的数目。且不 考虑顶点到其自身的弧。）考虑顶点到其自身的弧。） v2 v1 v3 v4 含有很少条边或弧的图。含有很少条边或弧的图。 含有很多条边或弧的接近完全图的图。含有很多条边或弧的接近完全图的图。 与图的与图的或或相关的数，这些数可以表示从一个顶点到相关的数，这些数可以表示从一个顶点到 另一个顶点的距离或耗费。另一个顶点的距离或耗费。 带权的图。带权的图。 北北 京京 上上 海海 12000 15000 北北 京京 上上 海海 1785 v3 v4 v5 如果图如果图 G = (V, E) 和和 G

15、 = (V , E )，满足：满足：V V 且且 E E，则称，则称 G 为为G 的子图的子图。v2 v1 v3 v4 v2 v1 v3 v4 v5 v1 v1 v3 v2 v1 v4 v2 v1 v5 v2 v1 v4 v5 v2 v1 v5 若若 (v, v ) 是一条边，则称顶点是一条边，则称顶点 v 和和 v 互为邻接点，互为邻接点， 或称或称 v 和和 v 相邻接；称边相邻接；称边 (v, v ) 于顶点于顶点 v 和和 v ，或称，或称 (v, v ) 与顶点与顶点 v 和和 v 。 若若 是一条弧，则称顶点是一条弧，则称顶点 v 邻接邻接 v ，顶点，顶点 v 邻接邻接 顶点顶点

16、 v。并称弧。并称弧 与顶点与顶点 v 和和 v 。v2 v1 v4 无向图无向图中顶点中顶点 v 的度是和的度是和 v 相关联的边的数目，记为：相关联的边的数目，记为： TD(v)。 v2 v1 v3 v4 v5 有向图有向图中以顶点中以顶点 v 为头的弧的数目称为为头的弧的数目称为 v 的入度，记的入度，记 为：为：ID(v)。 有向图有向图中以顶点中以顶点 v 为尾的弧的数目称为为尾的弧的数目称为 v 的出度，记的出度，记 为：为：OD(v)。 入度和出度之和，即：入度和出度之和，即：TD(v) = ID(v) + OD(v)。 v2 v1 v3 v4 如果顶点如果顶点 vi 的度为的度

17、为 TD(vi)，则一个有，则一个有 n 个顶点个顶点 e 条边（弧）条边（弧） 的图，满足如下关系：的图，满足如下关系： niivTDe1)(21 从顶点从顶点 v 到到 v 的路径是一个顶点序列的路径是一个顶点序列 (v = vi, 0, vi, 1, , vi, m= v )，满足满足 (vi, j-1, vi, j) VR 或或 VR，(1 j m)。 对于有向图，路径也是有向的。对于有向图，路径也是有向的。 v2 v1 v3 v4 v5 v2 v1 v3 v4 路径上边或弧的数目。路径上边或弧的数目。 第一个顶点和最后一个顶点相同的路径。第一个顶点和最后一个顶点相同的路径。 序列中顶

18、点（两端点除外）不重复出现的路径。序列中顶点（两端点除外）不重复出现的路径。 前后两端点相同的简单路径。前后两端点相同的简单路径。 从顶点从顶点 v 到到 v 有路径，则说有路径，则说 v 和和 v 是连通的是连通的。 图中任意两个顶点都是连通的。图中任意两个顶点都是连通的。 v2 v1 v3 v4 v5 有有 n 个顶点和小于个顶点和小于 n-1 条边的图。条边的图。 无向图的极大连通子图（无向图的极大连通子图（不存在包含它的更大的不存在包含它的更大的 连通子图连通子图）；任何连通图的连通分量只有一个，即其本身；非连；任何连通图的连通分量只有一个，即其本身；非连 通图有多个连通分量（通图有多

19、个连通分量（非连通图的每一个连通部分非连通图的每一个连通部分）。）。 v2 v1 v3 v4 v5 v2 v1 v3 v4 v5 任意两个顶点都连通的有向图。任意两个顶点都连通的有向图。 v2 v1 v3 v4 有向图的极大强连通子图；任何强连通图的强有向图的极大强连通子图；任何强连通图的强 连通分量只有一个，即其本身；非强连通图有多个强连通分量。连通分量只有一个，即其本身；非强连通图有多个强连通分量。 v2 v1 v3 v4 v2 v1 v3 v4 所有顶点均由边连接在一起，但不存在回路的图。所有顶点均由边连接在一起，但不存在回路的图。 v2 v1 v3 v4 v5 v2 v1 v3 v4

20、v5 v2 v1 v3 v4 v5 v2 v1 v3 v4 v5 v 一个图可以有许多棵不同的生成树。一个图可以有许多棵不同的生成树。 注注v 所有生成树具有以下共同特点：所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同；生成树的顶点个数与图的顶点个数相同； 生成树是图的极小连通子图；生成树是图的极小连通子图； 一个有一个有 n 个顶点的连通图的生成树有个顶点的连通图的生成树有 n-1 条边；条边； 生成树中任意两个顶点间的路径是唯一的；生成树中任意两个顶点间的路径是唯一的； 在生成树中再加一条边必然形成回路。在生成树中再加一条边必然形成回路。 v 含含 n 个顶点个顶点 n-

21、1 条边的图不一定是生成树。条边的图不一定是生成树。 v2 v1 v3 v4 v5 对于非连通图，其每个连通分量可以构造一棵生对于非连通图，其每个连通分量可以构造一棵生 成树，合成起来就是一个生成森林。成树，合成起来就是一个生成森林。 如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为 0 ，其余顶，其余顶 点的入度均为点的入度均为 1 ，则是一棵有向树。，则是一棵有向树。 由若干棵有向树组成，含有图中全部顶由若干棵有向树组成，含有图中全部顶 点，但只有足以构成若干棵不相交的有向树的弧。点，但只有足以构成若干棵不相交的有向树的弧。 B A CF ED B A DF EC 7.

22、2 图的存储结构图的存储结构 多重链表多重链表 v1v2 v4 v3 v1 v2 v4 v5 v3 v2 v1 v3 v4 G1 v2 v1 v3 v4 v5 G2 7.2.1 数组表示法（邻接矩阵表示法）数组表示法（邻接矩阵表示法） 中中的的边边或或弧弧不不是是或或：若若中中的的边边或或弧弧是是或或：若若 VR v v v v VR v v v v ji,Ajijijiji,),(0,),(1 对于一个具有对于一个具有 n 个顶点的图，可用两个数组存储。其中一个个顶点的图，可用两个数组存储。其中一个 一维数组一维数组存储数据元素（存储数据元素（顶点顶点）的信息，另一个）的信息，另一个（图的（

23、图的 ）存储数据元素之间的关系（）存储数据元素之间的关系（）的信息。）的信息。 设设 G = (V, VR) 是具有是具有 n 个顶点的图，顶点的顺个顶点的图，顶点的顺 序依次为序依次为 v1, v2, , vn，则，则 G 的邻接矩阵是具有如下性质的的邻接矩阵是具有如下性质的 n 阶阶 方阵：方阵： 0011000101110101010101010 0001100000000110v2 v1 v3 v4 G1 v2 v1 v3 v4 v5 G2 v1 v2 v3 v4 v1 v2 v3 v4 v5 v1 v2 v3 v4 v1 v2 v3 v4 v5 特点：特点： 无向图的邻接矩阵对称，可

24、压缩存储；有无向图的邻接矩阵对称，可压缩存储；有 n 个顶点的无向图需个顶点的无向图需 存储空间为存储空间为 n(n-1)/2。 有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有 n 个顶点的有向图需存储空间个顶点的有向图需存储空间 为为 n，空间复杂度为，空间复杂度为 O(n2)，用于稀疏图时空间浪费严重。，用于稀疏图时空间浪费严重。 无向图中顶点无向图中顶点 vi 的度的度 TD(vi) 是邻接矩阵中第是邻接矩阵中第 i 行行 1 的个数。的个数。 有向图中有向图中 顶点顶点 vi 的的是邻接矩阵中第是邻接矩阵中第 i 1 的个数。的个数。 顶点顶点 vi 的的是邻接矩阵中第是邻接

25、矩阵中第 i 1 的个数。的个数。 网的邻接矩阵可定义为：网的邻接矩阵可定义为： 中中的的边边或或弧弧不不是是或或：若若中中的的边边或或弧弧是是或或：若若 VR v v v v VR v v v v wji,Ajijijijiij,),(,),(v2 v1 v3 v4 v5 v6 5 4 8 9 7 5 5 6 1 3 1356598475v1 v2 v3 v4 v5 v6 v1 v2 v3 v4 v5 v6 图的数组（邻接矩阵）存储表示：图的数组（邻接矩阵）存储表示： #define INFINITY INT_MAX / 最大值最大值 #define MAX_VERTEX_NUM 20 /

26、最大顶点个数最大顶点个数 typedef enum DG, DN, AG, AN GraphKind; /有向图有向图,有向网有向网,无向图无向图,无向网无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用 1 或或 0 表示相邻否；表示相邻否； / 对带权图，则为权值类型。对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct

27、VertexType vexsMAX_VERTEX_NUM; / 顶点向量顶点向量 AdjMatrix arcs; / 邻接矩阵邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧图的当前顶点数和弧(边边)数数 GraphKind kind; / 图的种类标志图的种类标志 MGraph; 7.2.2 邻接表（邻接表（类似于树的孩子链表表示法类似于树的孩子链表表示法） 头结点头结点 表结点表结点 v2 v1 v3 v4 v5 G2 v1 v3 v4 v2 v5 0 1 2 3 4 3 1 4 2 0 4 3 1 2 0 2 1 ，指示下一条边或弧。，指示下一条边或弧。 特点：

28、特点： 若无向图中有若无向图中有 n 个顶点、个顶点、e 条边，则其邻接表需条边，则其邻接表需 n 个头结点和个头结点和 2e 个表结点。适宜存储稀疏图。个表结点。适宜存储稀疏图。 无向图中顶点无向图中顶点 vi 的度为第的度为第 i 个单链表中的结点数。个单链表中的结点数。 ，存放与，存放与 vi 邻接的邻接的 顶顶点在表头数组中的位置。点在表头数组中的位置。 v2 v1 v3 v4 G1 0 1 2 3 2 1 3 0 v1 v3 v4 v2 0 1 2 3 3 0 2 v1 v3 v4 v2 0 邻接表邻接表 逆邻接表逆邻接表 顶点顶点 vi 的的为第为第 i 个单链个单链 表中的结点个

29、数。表中的结点个数。 特点：特点： 顶点顶点 vi 的的为整个为整个单链表单链表 中邻接点域值是中邻接点域值是 i -1 的结点的结点 个数个数。 找出度易，找入度难。找出度易，找入度难。 找入度易，找出度难。找入度易，找出度难。 顶点顶点 vi 的的为第为第 i 个单链个单链 表中的结点个数。表中的结点个数。 顶点顶点 vi 的的为整个为整个单链表单链表 中邻接点域值是中邻接点域值是 i -1 的结点的结点 个数个数。 图的邻接表存储表示：图的邻接表存储表示： #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 该弧所

30、指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcNode; typedef struct VNode VertexType data; / 顶点信息顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和

31、弧数图的当前顶点数和弧数 int kind; / 图的种类标志图的种类标志 ALGraph; 弧结点弧结点 第一条入弧第一条入弧 第一条出弧第一条出弧 弧尾位置弧尾位置 弧头位置弧头位置 弧头相同的下一条弧弧头相同的下一条弧 弧尾相同的下一条弧弧尾相同的下一条弧 a b c d 01237.2.3 十字链表十字链表 0 12 00 2 3 0 3 1 3 2 2 3 bdactailvex headvex hlink tlinkdata firstin firstout顶点结点顶点结点 #define MAX_VERTEX_NUM 20 typedef struct ArcBox int ta

32、ilvex, headvex; / 该弧的尾和头顶点的位置该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcBox; typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧分别指向该顶点第一条入弧和出弧 VexNode; typedef struct VexNode xlis

33、tMAX_VERTEX_NUM; / 表头向量表头向量 int vexnum, arcnum; / 有向图的当前顶点数和弧数有向图的当前顶点数和弧数 OLGraph; 有向图的十字链表存储表示：有向图的十字链表存储表示： 指向依附于指向依附于 ivex 的下一条边的下一条边 7.2.3 邻接多重表（无向图的另一种链式存储结构）邻接多重表（无向图的另一种链式存储结构） 邻接表优点：邻接表优点：容易求得顶点和边的信息。容易求得顶点和边的信息。 缺点：缺点：某些操作不方便（如：删除一条边需找表示此某些操作不方便（如：删除一条边需找表示此 边的两个结点）。边的两个结点）。 邻接多重表：邻接多重表：每条

34、边用一个结点表示。每条边用一个结点表示。其结点结构如下：其结点结构如下： 指向依附于指向依附于 jvex 的下一条边的下一条边 mark ivex ilink jvex jlink info 边结点边结点 data firstedge 顶点结点顶点结点 存与顶点有关的信息存与顶点有关的信息指向第一条依附于该顶点的边指向第一条依附于该顶点的边 标志域标志域 标记此边是标记此边是 否被搜索过否被搜索过 该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 0 3 0 1 2 3 4 v2 v1 v3 v4 v5 G2 0 1 2 3 2 1 2 4 4 1 指向依附于指向依附于 i

35、vex 的下一条边的下一条边 指向依附于指向依附于 jvex 的下一条边的下一条边 mark ivex ilink jvex jlink info 边结点边结点 标志域标志域 标记此边是标记此边是 否被搜索过否被搜索过 该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 data firstedge 顶点结点顶点结点 存与顶点有关的信息存与顶点有关的信息指向第一条依附于该顶点的边指向第一条依附于该顶点的边#define MAX_VERTEX_NUM 20 typedef emnu unvisited, visited VisitIf; typedef struct Ebox

36、VisitIf mark; / 访问标记访问标记 int ivex, jvex; / 该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox *ilink, *jlink; / 分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边 InfoType *info; / 该边信息指针该边信息指针 EBox; typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边指向第一条依附该顶点的边 VexBox; typedef struct VexBox adjmulistMAX_VERTEX

37、_NUM; int vexnum, edgenum; / 无向图的当前顶点数和边数无向图的当前顶点数和边数 AMLGraph; 无向图的邻接多重表存储表示：无向图的邻接多重表存储表示： 7.3 图的遍历图的遍历 从图的任意指定顶点出发，依照某种规则去访问图中所有顶从图的任意指定顶点出发，依照某种规则去访问图中所有顶 点，且每个顶点仅被访问一次，这一过程叫做点，且每个顶点仅被访问一次，这一过程叫做。 图的遍历按照深度优先和广度优先规则去实施，通常有图的遍历按照深度优先和广度优先规则去实施，通常有（Depth_First SearchDFS ）和）和 （ Breadth_Frist SearchB

38、FS）两种。）两种。V1V2V4V5V3V7V6V87.3.1 深度优先遍历（深度优先遍历（DFS） 1、访问指定的起始顶点；访问指定的起始顶点； 2、若、若当前访问的顶点当前访问的顶点的邻接顶点有的邻接顶点有，则任选，则任选 一个访问之；反之，一个访问之；反之，到最近访问过的顶点；直到到最近访问过的顶点；直到 与起始顶点相通的全部顶点都访问完毕；与起始顶点相通的全部顶点都访问完毕； 3、若此时图中尚有顶点未被访问，则再选其中一个顶点若此时图中尚有顶点未被访问，则再选其中一个顶点 作为起始顶点并访问之，转作为起始顶点并访问之，转 2； 反之，遍历结束。反之，遍历结束。 例：例： V1 V1V2

39、V4V5V3V7V6V8顶点访问次序：顶点访问次序： V2 V4 V8 V5 V3 V6 V7 V1 V2 V5 V8 V4 V3 V6 V7 V1 V2 V4 V8 V5 V3 V7 V6 V1 V2 V5 V8 V4 V3 V7 V6 V1 V3 V6 V7 V2 V4 V8 V5 连通图的深度优先遍历类似于树的先根遍历连通图的深度优先遍历类似于树的先根遍历 abchdekfga c h dfke b g顶点访问次序顶点访问次序: :例：例： a c h dfke g ba c h fked b g解决办法：解决办法：为每个顶点设立一个为每个顶点设立一个“访问标志访问标志”。 如何判别如何

40、判别V的邻接点是否被访问？的邻接点是否被访问？ 首先将图中每个顶点的访问标志设为首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图之后搜索图 中每个顶点，如果未被访问，则以该顶点为起始点，进行深度中每个顶点，如果未被访问，则以该顶点为起始点，进行深度 优先遍历，否则继续检查下一顶点。优先遍历，否则继续检查下一顶点。 1 3 7 4 0 V1 V2 V4 V8 V5 V3 实现：实现： V1V2V4V5V3V7V6V80 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 1 2 3 4

41、5 6 7 2 V6 5 V7 6 1 1 1 1 1 1 1 1 1 3 7 0 V1 V2 V4 V8 V5 V3 0 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 3 1 5 6 7 7 6 0 1 2 3 4 5 6 7 2 V6 5 V7 6 V1V2V4V5V3V7V6V84 1 1 1 1 1 1 1 1 7.3.2 广度优先遍历（广度优先遍历（BFS） 从图的某一结点出发，首先依次访问该结点的所有邻从图的某一结点出发，首先依次访问该结点的所有邻 接顶点接顶点 Vi1, Vi2, , Vin 再按这些顶点被访问的先后次序依次访问再按这些顶点被

42、访问的先后次序依次访问 与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶 点均被访问为止。点均被访问为止。 例：例： V1V2V4V5V3V7V6V8广度优先遍历：广度优先遍历： V1 V2 V3 V4 V5 V6 V7 V8 V1 V3 V2 V7 V6 V5 V4 V8 V1 V2 V3 V5 V4 V7 V6 V8 abchdekfga c d e fh k bg顶点访问次序顶点访问次序: :例：例： a c d e fh k gb1 3 4 0 V1 V2 V3 V4 V5 V6 实现：实现： V1V2V4V5V3V7V6

43、V80 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 1 2 3 4 5 6 7 2 V7 5 V8 F R R F R R F R R F 6 7 F F F F F R R R 1 1 1 1 1 1 1 1 开始开始访问访问V0，置置标志标志求求V邻接点邻接点ww存在吗存在吗V下一邻接点下一邻接点ww访问过访问过结束结束NYNYBFS初始化队列初始化队列V0入队入队队列空吗队列空吗队头队头V出队出队访问访问w，置置标志标志w入队入队NY7.4 图的连通性问题图的连通性问题 7.4.1

44、 无向图的连通分量和生成树无向图的连通分量和生成树 V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8 设图设图 G=(V, E) 是个连通图，当从图任一顶点出发遍历图是个连通图，当从图任一顶点出发遍历图 G 时，将边集时，将边集 E(G) 分成两个集合分成两个集合 T(G) 和和 B(G)。其中。其中 T(G) 是遍历图时所经过的边的集合，是遍历图时所经过的边的集合，B(G) 是遍历图时未经过的边是遍历图时未经过的边 的集合。显然，的集合。显然， G1(V, T) 是图是图 G 的极小连通子图。的极小连通子图。 即子图即子图 G1 是连通图是连通图 G 的的生成树生成树。 深度

45、优先生成树深度优先生成树 广度优先生成树广度优先生成树 所有顶点均由边所有顶点均由边 连接在一起，但连接在一起，但 不存在回路的图。不存在回路的图。 ABLMCFDEGHKIJ深度优先生成森林深度优先生成森林 ABLMCFJDEGHKI 一个连通图的生成树不一定是唯一的。一个连通图的生成树不一定是唯一的。 一个非连通图的生成森林不一定是唯一的。一个非连通图的生成森林不一定是唯一的。V1V6V5V4V3V26513566425V1V6V5V4V3V265134V1V6V5V4V3V26513219 17 7.4.3 最小生成树最小生成树 最小生成树：最小生成树：给定一个无向网络，在该网的所有生成

46、给定一个无向网络，在该网的所有生成 树中，使得各边权数之和最小的那棵生成树称为该网的最树中，使得各边权数之和最小的那棵生成树称为该网的最 小生成树，也叫小生成树，也叫最小代价生成树最小代价生成树。 要在要在 n 个城市间建立通信联络网。个城市间建立通信联络网。顶点顶点：表示城市，表示城市， 权：权：城市间通信线路的花费代价。希望此通信网花费代价最小。城市间通信线路的花费代价。希望此通信网花费代价最小。 答案只能从生成树中找，因为要做到任何两个城市之答案只能从生成树中找，因为要做到任何两个城市之 间有线路可达，间有线路可达，通信网必须是连通的通信网必须是连通的；但对长度最小的要求可以；但对长度最

47、小的要求可以 知道知道网中显然不能有圈网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连，如果有圈，去掉一条边后，并不破坏连 通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。 希望找到一棵生成树，它的每条边上的权值之和（即建立希望找到一棵生成树，它的每条边上的权值之和（即建立 该通信网所需花费的总代价）最小该通信网所需花费的总代价）最小 最小代价生成树。最小代价生成树。 构造最小生成树的算法很多，其中多数算法都利用了一种构造最小生成树的算法很多，其中多数算法都利用了一种 称之为称之为 MST 的性质。的性质。 设设 N = (V

48、, E) 是一个连通网，是一个连通网，U 是顶点集是顶点集 V 的一的一 个非空子集。若边个非空子集。若边 (u, v) 是一条具有最小权值的边，其中是一条具有最小权值的边，其中uU， vV-U，则必存在一棵包含边，则必存在一棵包含边 (u, v) 的最小生成树。的最小生成树。 V1V6V5V4V3V26513566425N = (V, E) V = v1, v2, v3, v4, v5, v6 E = (v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v5), (v3, v4), (v3, v5), (v3, v6), (v4, v6), (v5, v

49、6) U = v1 V1构造最小生成树方法：构造最小生成树方法： 方法一：普里姆方法一：普里姆 (Prim) 算法。算法。 V1V6V5V4V3V26513566425 设设 N=(V, E) 是连通网，是连通网，TE 是是 N 上上 最小生成树中最小生成树中边的集合边的集合。 初始令初始令 U=u0, (u0 V ), TE= 。 在所有在所有 u U, v V-U 的边的边 (u, v) E 中，中， 找一条代价最小的边找一条代价最小的边 (u0, v0)。 将将 (u0, v0) 并入集合并入集合 TE，同时同时 v0 并入并入 U。 重复上述操作直至重复上述操作直至 U=V 为止，则为

50、止，则 T=(V, TE) 为为 N 的最小生的最小生 成树。成树。 V1V3V6V4V2V5方法二：克鲁斯卡尔方法二：克鲁斯卡尔 (Kruskal) 算法。算法。 V1V6V5V4V3V26513566425 设连通网设连通网 N = (V, E )，令最小生成树令最小生成树初初始状态为始状态为只有只有 n 个个顶点顶点而而无边无边的非连通图的非连通图 T=(V, )，每个顶点自成一个连通分量。，每个顶点自成一个连通分量。 在在 E 中选取代价最小的边，若该边依附中选取代价最小的边，若该边依附 的顶点落在的顶点落在 T 中不同的连通分量上（即：中不同的连通分量上（即： 不能形成环不能形成环）

51、，则将此边加入到），则将此边加入到 T 中；否中；否 则，舍去此边，选取下一条代价最小的边则，舍去此边，选取下一条代价最小的边。 依此类推，直至依此类推，直至 T 中所有顶点都在同一中所有顶点都在同一 连通分量上为止。连通分量上为止。 最小生成树最小生成树 可能不惟一可能不惟一 V1V6V5V4V3V212345N T 填空题部分填空题部分 1. n 个顶点的连通图至少个顶点的连通图至少 ( ) 条边。条边。2. 在一个无向图的邻接表中，若表结点的个数是在一个无向图的邻接表中，若表结点的个数是 m，则图中边的，则图中边的 条数是条数是 ( ) 条。条。 3. 分别用普里姆和克鲁斯卡尔算法构造题

52、图分别用普里姆和克鲁斯卡尔算法构造题图 5-3 所示网络的最小所示网络的最小 生成树。生成树。 作业：作业： 7.1、7.3、7.5、7.7 4. 分别求出题图分别求出题图 5-1 从从 v2 出发按深度优先搜索和广度优先搜出发按深度优先搜索和广度优先搜 索算法遍历得到的顶点序列（假设图的存储结构采用邻接矩阵索算法遍历得到的顶点序列（假设图的存储结构采用邻接矩阵 表示）。表示）。 5. 已知一个有向图的邻接表如题图已知一个有向图的邻接表如题图 5-2 所示，求出根据深度优所示，求出根据深度优 先搜索算法从顶点先搜索算法从顶点 v1 出发遍历得到的顶点序列。出发遍历得到的顶点序列。 选择题选择题

53、 1. 在一个图中，所有顶点的度数之和等于所有边数的在一个图中，所有顶点的度数之和等于所有边数的 ( ) 倍。倍。 （A）1/2 （B）1 （C）2 （D）4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 ( ) 倍。倍。 （A）1/2 （B）1 （C）2 （D）4 3. 一个有一个有 n 个顶点的无向图最多有个顶点的无向图最多有 ( ) 条边。条边。 （A）n （B）n(n -1) （C）n(n-1)/2 （D）2n 4. 具有具有 4 个顶点的无向完全图有个顶点的无向完全图有 ( ) 条边。条边。 （A）6 （B

54、）12 （C）16 （D）20 5. 具有具有 6 个顶点的无向图至少应有个顶点的无向图至少应有 ( ) 条边才能确保是一个连通图。条边才能确保是一个连通图。 （A）5 （B）6 （C）7 （D）86. 在一个具有在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要个顶点的无向图中，要连通全部顶点至少需要 ( ) 条边。条边。 （A）n （B）n + 1 （C）n 1 （D）n/2 对于一个具有对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小 为为 ( )。 （A）n （B）(n-1)2 （C）n -1 （D）n2 对于

55、一个具有对于一个具有 n 个顶点和个顶点和 e 条边的无向图，若采用邻接表表示，则表头数条边的无向图，若采用邻接表表示，则表头数 组的大小为组的大小为 ( )，所有邻接表中的结点总数是，所有邻接表中的结点总数是 ( )。 （A）n （B）n+1 （C）n-1 （D）n+e （A）e/2 （B）e （C）2e （D）n+e 图的深度优先遍历算法类似于树的（图的深度优先遍历算法类似于树的（ ）。）。（A）先根遍历）先根遍历 （B）后根遍历）后根遍历 （C）按层遍历）按层遍历图的广度优先遍历算法类似于树的（图的广度优先遍历算法类似于树的（ ）。）。（A）先根遍历）先根遍历 （B）后根遍历）后根遍历

56、（C）按层遍历）按层遍历7.5 有向无环图及其应用有向无环图及其应用 有向无环图：有向无环图：无环的有向图，无环的有向图， 简称简称 DAG （Directed Acycline Graph）图。）图。 有向树有向树 有向无环图有向无环图 有向图有向图 1、描述、描述含有公共子式的表达式含有公共子式的表达式： )()()()(edcedcdcbba abbcccdddeeabcde有向无环图的用途：有向无环图的用途： 共享相同子式共享相同子式 节省存储空间节省存储空间 除最简单的情况之外，几乎所有的工程都可分为若干个称除最简单的情况之外，几乎所有的工程都可分为若干个称 作作“”的子工程，并且这

57、些子工程之间通常受着一定条件的的子工程，并且这些子工程之间通常受着一定条件的 约束，例如：其中某些子工程必须在另一些子工程完成之后才约束，例如：其中某些子工程必须在另一些子工程完成之后才 能开始。能开始。 对整个工程和系统，人们关心的是两方面的问题：对整个工程和系统，人们关心的是两方面的问题： 一是一是工程能否顺利进行工程能否顺利进行； 二是完成整个工程所必须的二是完成整个工程所必须的。 2、在工程计划和管理方面的应用、在工程计划和管理方面的应用 对应到有向图即为进行对应到有向图即为进行拓扑排序拓扑排序和求和求。 7.5.1 拓扑排序拓扑排序 AOV 网网： 用一个有向图表示一个工程的各子工程

58、及其相互用一个有向图表示一个工程的各子工程及其相互 制约的关系，其中以制约的关系，其中以顶点顶点表示表示活动活动，弧弧表示活动之间表示活动之间 的优先制约的优先制约关系关系，称这种，称这种有向图为有向图为 ， 简称简称 (Activity On Vertex network) 。 例：例：排课表。排课表。 课程代号课程代号 课程名称课程名称 先修课先修课 C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,C4C11C3,C5C3,C6无无C9C9C1,C9,C10 程序设计基础程序设计基础离散数学离散数学数据结构数据结构汇编语言汇编语言语言的设计和分析语言的设计

59、和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学线性代数线性代数普通物理普通物理数值分析数值分析C1C2C3C4C5C6C7C8C9C10C11C12 若若 是网中有向边，则是网中有向边，则 i 是是 j 的直接前驱；的直接前驱； j 是是 i 的直接后继。的直接后继。 ，因为如因为如 果有回路存在，则表明果有回路存在，则表明某项活动以某项活动以 自己为先决条件，自己为先决条件，显然这是荒谬的。显然这是荒谬的。 如何判别如何判别 AOV 网中是否存在回路？网中是否存在回路？ C1C2C3C4C5C6C7C8C9C10C11C12AOV 网的特点：网的特点： 若从若从

60、i 到到 j 有一条有向路径，则有一条有向路径，则 i 是是 j 的前驱；的前驱；j 是是 i 的后继。的后继。 拓扑排序：拓扑排序： 对有向图构造其顶点对有向图构造其顶点 的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中， 则该则该 AOV 网必定不存在环网必定不存在环。 在在 AOV 网没有回路的前提下，我们将全部活动网没有回路的前提下，我们将全部活动 排列成一个线性序列，使得若排列成一个线性序列，使得若 AOV 网中有弧网中有弧 存在，则在这个序列中，存在，则在这个序列中， i 一定排在一定排在 j 的前面，具有的前面，具有 这种性质的线性序列称为这种性质的线性序列称为拓扑有序序列