2.1-抽象数据类型图的定义ppt课件

1、第七章第七章 图图7.1 抽象数据类型图的定义抽象数据类型图的定义ADT Graph 数据对象数据对象V：V是具有相同特性的数据元素的集是具有相同特性的数据元素的集合，合，称为顶点集。称为顶点集。数据关系数据关系R：RVRVR| v,wV且且P(v,w)，表示从表示从v到到w的弧，的弧，谓词谓词P(v,w)定义了弧定义了弧的意义或信息的意义或信息 名词和术语名词和术语有向图、有向图、 无向图、无向图、 网、网、 子图子图 弧头、弧头、 弧尾、弧尾、 边边完全图、完全图、 稀疏图、稀疏图、 稠密图稠密图 邻接点、邻接点、 度、度、 入度、入度、 出度出度途径、途径、 路径长度、路径长度、 回路回

2、路简单路径、简单路径、 简单回路简单回路连通图、连通图、 连通分量、连通分量、强连通图、强连通图、 强连通分量强连通分量生成树、生成树、 生成森林、生成森林、 最小生成树最小生成树基本操作基本操作P：结构的建立和销毁结构的建立和销毁:CreateGraph(&G,V,VR); / 按按V和和VR的定义构造的定义构造图图G。DestroyGraph(&G); / 销毁图销毁图G。对顶点的访问操作对顶点的访问操作:LocateVex(G, u); / 若若G中存在顶点中存在顶点u，则返回该顶，则返回该顶点点/ 在图中位置；否则返回其它信息。在图中位置；否则返回其它信息。GetVex

3、(G, v); / 返回返回v的值。的值。PutVex(&G, v, value); / 对对v赋值赋值value。对邻接点的操作:FirstAdjVex(G, v); / 返回v的第一个邻接点。若该顶点/在G中没有邻接点，则返回“空”。NextAdjVex(G, v, w); /返回v的相对于w的下一个/ 邻接点。若w是v的最后一个邻/ 接点，则返回“空”。插入或删除顶点InsertVex(&G, v); / 在图G中增添新顶点v。DeleteVex(&G, v); / 删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G, v, w); / 在G

4、中增添弧，若G是无/ 向的，则还增添对称弧。DeleteArc(&G, v, w); /在G中删除弧，若G是无/ 向的，则还删除对称弧。遍历DFSTraverse(G, v, Visit(); / 从顶点v起深度优先遍历图/ G，并对每个顶点调用函数/ Visit一次且仅一次。BFSTraverse(G, v, Visit(); / 从顶点v起广度优先遍历图/ G，并对每个顶点调用函数/ Visit一次且仅一次。7.2 图的存储表示图的存储表示图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示#define INFINITY INT_MAX / 最大值最大值#define MAX_V

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

6、struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量顶点向量AdjMatrix arcs; / 邻接矩阵邻接矩阵int vexnum, arcnum; / 图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKind kind; / 图的种类标志图的种类标志 MGraph;图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置struct ArcNode *nextarc; / 指向下一条弧的指针InfoType *info; / 该弧相关信息

7、的指针 ArcNode;typedef struct VNode VertexType data; / 顶点信息ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum, arcnum; / 图的当前顶点数和弧数int kind; / 图的种类标志 ALGraph;有向图的十字链表存储表示 #define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex; / 该弧的尾和头

8、顶点的位置struct ArcBox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域InfoType *info; / 该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data;ArcBox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧 VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 表头向量int vexnum, arcnum; / 有向图的当前顶点数和弧数 OLGraph;无向图的邻接多重表存储表示 #defin

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

10、Box adjmulistMAX_VERTEX_NUM;int vexnum, edgenum; / 无向图的当前顶点数和边数 AMLGraph; 7.3 图的遍历图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。且使图中的每个顶点仅被访问一次的过程。一、深度优先搜索一、深度优先搜索从图中某个顶点从图中某个顶点V0 动身，访问此顶点，然后依次从动身，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和直至图中所有和V0有路径相通

11、的顶点都被访问到，若有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。顶点都被访问到为止。/- 下列算法使用的全局变量 -Boolean visitedMAX; / 访问标志数组Status (* VisitFunc)(int v); / 函数变量void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图G作深度优先遍历。VisitFunc = Visit; for

12、 (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFSvoid DFS(Graph G, int v) / 从第从第v个顶点出发递归地深度优先遍历图个顶点出发递归地深度优先遍历图G。visitedv = TRUE; VisitFunc(v); / 访问第访问第v个顶点个顶点for ( w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v, w) )if (!visitedw) DF

13、S(G, w); / 对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS二、广度优先搜索二、广度优先搜索从图中的某个顶点从图中的某个顶点V0出发，并在访问此顶点出发，并在访问此顶点之后依次访问之后依次访问V0的所有未被访问过的邻接点，的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和它们的邻接点，直至图中所有和V0有路径相有路径相通的顶点都被访问到。若此时图中尚有顶点通的顶点都被访问到。若此时图中尚有顶点未被访问未被访问,则另选图中一个未曾被访问的顶点则另选图中一个未曾被访问的顶点作起始点，重复

14、上述过程，直至图中所有顶作起始点，重复上述过程，直至图中所有顶点都被访问到为止。点都被访问到为止。void BFSTraverse(Graph G, Status (*Visit)(int v) / 按广度优先非递归遍历图按广度优先非递归遍历图G。使用辅助队列。使用辅助队列Q和访问标志数组和访问标志数组visited。for (v=0; vG.vexnum; +v) visitedv = FALSE;InitQueue(Q); / 置空的辅助队列置空的辅助队列Qfor ( v=0; vG.vexnum; +v )if ( !visitedv) / v尚未访问尚未访问EnQueue(Q, v);

15、 / v入队列入队列while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为队头元素出队并置为uvisitedu = TRUE; Visit(u); / 访问访问ufor ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) )if ( ! visitedw) EnQueue(Q, w); / u的尚未访问的邻接顶点的尚未访问的邻接顶点w入队列入队列Q7.4 最小生成树最小生成树问题：假设要在问题：假设要在n个城市之间建立通讯个城市之间建立通讯联络网，则连通联络网，则连通n个城市只需要修建个城市只需要修建n

16、-1条线路，如何在最节省经费的前提下条线路，如何在最节省经费的前提下建立这个建立这个通讯网？通讯网？该问题等价于：构造网的一棵最小生该问题等价于：构造网的一棵最小生成树，即：在成树，即：在e条带权的边中选取条带权的边中选取n-1条条不构成回路），使不构成回路），使“权值之和为权值之和为最小。最小。算法一：（普里姆算法）算法一：（普里姆算法）可取图中任意一个顶点可取图中任意一个顶点v作为生成树的根，之后若作为生成树的根，之后若要往生成树上添加顶点要往生成树上添加顶点w，则在顶点，则在顶点v和顶点和顶点w之之间必定存在一条边，并且该边的权值在所有连通间必定存在一条边，并且该边的权值在所有连通顶点顶

17、点v和和w之间的边中取值最小。之间的边中取值最小。一般情况下，假设一般情况下，假设n个顶点分成两个集合：个顶点分成两个集合：U包包含已落在生成树上的结点和含已落在生成树上的结点和V-U尚未落在生成尚未落在生成树上的顶点），则在所有连通树上的顶点），则在所有连通U中顶点和中顶点和V-U中顶中顶点的边中选取权值最小的边。点的边中选取权值最小的边。记录从顶点集记录从顶点集U到到VU的代价最小的边的辅助数的代价最小的边的辅助数组：组：struct VertexType adjvex;VRType lowcost; closedgeMAX_VERTEX_NUM;k = LocateVex ( G, u

18、); / 顶点顶点u为构造生成树的起始点为构造生成树的起始点for ( j=0; jG.vexnum; +j ) / 辅助数组初始化辅助数组初始化if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，初始，Uufor (i=0; iG.vexnum; +i) /在其余顶点中选择在其余顶点中选择k = minimum(closedge); / 求出求出T的下一个结点的下一个结点(k)printf(closedgek.adjvex, G.vexsk); / 输出生成树的输出生成树的边边closedgek.lowcos

19、t = 0; / 第第k顶点并入顶点并入U集集for (j=0; jG.vexnum; +j)if (G.arcskj.adj closedgej.lowcost)closedgej = G.vexsk, G.arcskj.adj ;/ 新顶点并入新顶点并入U后重新选择最小边后重新选择最小边算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）为使生成树上边的权值之和最小，显然，为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只鲁斯卡尔算法的做法就是：先构造一个只含含n个顶点的子图个顶点的子图SG，然后

20、从权值最小的，然后从权值最小的边开始，若它的添加不使边开始，若它的添加不使SG中产生回路，中产生回路，则在则在SG上加上这条边，如此重复，直至上加上这条边，如此重复，直至加上加上n-1条边为止。条边为止。算法算法:构造非连通图构造非连通图 ST=( V, );k = i = 0;while (kadjvex;DFSArticul(G, v); / 从第v顶点出发深度优先搜索if (count nextarc) w = p-adjvex; / w为v0的邻接顶点if (visitedw = 0) / w未曾被访问DFSArticul(G, w); / 返回前求得lowwif (loww =vis

21、itedv0) printf(v0, G.verticesv0.data); / 输出关节点elseif (visitedw min) min = visitedw; / w是回边上的顶点lowv0 = min; 7.6 两点之间的最短路径问题求从某个源点到其余各点的最短路径迪杰斯特拉推出了一个按路径长度递增的次序求从源点到其余各点最短路径的算法。假设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在一条长度最短者 在这条路径上，必定只含一条(权值最小)弧，由此，只要在所有从源点出发的弧中查找权值最小者; 长度次短的路径可能有两种情况: 它可能是从源点直接到该点的路径;也可能是

22、，从源点到a, 再从a到该点其余依次类推。 假设 Distk 表示 当前所求得的从源点到k的最 短路径显然，Distk = 或者 = + 二、每一对顶点之间的最短路径从vi到vj的最短路径是以下各种可能路径中的长度最小者:假设存在，则存在路径vi,vj/ 路径中不含其它顶点假设,存在，则存在路径vi,v1,vj/ 路径中所含顶点序号不大于1假设vi,v2, v2,vj存在，则存在一条路径vi, , v2, vj/ 路径中所含顶点序号不大于2依次类推，则vi至vj的最短路径应是上述这些路径中，路径长度最小者。7.7 拓扑排序拓扑排序 问题问题:假设以有向图表示一个工程的施工图或程序的数据流假设以

23、有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。图，则图中不允许出现回路。如何检查有向图中是否存在回路的方法之一，是对有如何检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。向图进行拓扑排序。 何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作对有向图进行如下操作:按照有向图给出的次序关系，将图中顶点排成一个线按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。可以人为加上任意的次序关系。 如何进行拓扑排序？一、从有向图中选取一个没有前驱的顶点，并输出之

24、;二、从有向图中删去此顶点以及所有以它为尾的弧;重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱 - 入度为零删除顶点及以它为尾的弧- 弧头顶点的入度减1 算法:取入度为零的顶点v;while (v0) printf(v); +m;w:=FirstAdj(v);while (w0) inDegreew-;w:=nextAdj(v,w);取下一个入度为零的顶点v;if mn printf(“图中有回路); 7.8 关键路径 问题:假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间，问:哪些子工程项是“关键工程”？即:将影响整个工程完成期限的子工程项。整个工程完成的时间为:从有向图的源点到汇点的最长路径。“关键活动指的是: 该弧上的权值增加 将使有向图上的最长路径的长度增加。 如何求关键活动？ “事件(顶点)” 的 最早发生时间 ve(j)ve(j) = 从源点到顶点j的最长路径长度;“事件(顶点)” 的 最迟发生时间 vl(k)