数据结构中的图.ppt

《数据结构中的图.ppt》由会员分享，可在线阅读，更多相关《数据结构中的图.ppt（67页珍藏版）》请在课桌文档上搜索。

1、,第7章 图（Graph）,数 据 结 构（Data Structure）,第七章 图,图是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素最多只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间存在明显的层次关系，并且每层的元素可能和下一层的多个元素相邻，但只能和上一层的一个元素相邻。而在图形结构中，结点之间的关系可以是任意的，图中的任意两个元素之间都可能相邻。图是计算机应用过程中对实际问题进行数学抽象和描述的强有力的工具，数据结构中对图的讨论侧重于在计算机中如何表示图以及如何实现图的操作和应用等。,第七章 图和广义表,7.1 图的定义和术语7.2 图

2、的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.5.1 拓扑排序7.5.2 关键路径7.6 最短路径,7.1 图的定义和术语,图由一个顶点的有穷非空集合V(G)和一个弧的集合E(G)组成，通常记做G=(V,E)。图中的顶点即为数据结构中的数据元素，弧的集合E实际上是定义在顶点集合上的一个关系。用有序对表示从v到w的一条弧。弧具有方向性，以带箭头的线段表示，通常称v为弧尾或始点，称w为弧头或终点，此时的图称为有向图。若图中从v到w有一条弧，同时从w到v也有一条弧，则以无序对(v,w)代替这两个有序对和,表示v和w之间的一条边。此时的图在顶点之间不再强调方向性的特征，

3、称为无向图。,7.1 图的定义和术语,图G1是一个有向图，G1=(V1,A1)。其中:V1=A,C,B,F,D,E,G A1=,有向图G1,7.1 图的定义和术语,图G2是一个无向图，G2=(V2,E2)。其中：V2=A,B,C,D,E,F E2=(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,E),A,B,C,D,E,F,无向图G2,7.1 图的定义和术语,在实际应用中，图的弧或边往往与具有一定意义的数相关，称这些数为权(weight)。分别称带权的有向图和无向图为有向网和无向网。,1,2,3,4,5,6,7,1,2,3,4,5,6,7,

4、19,18,21,27,5,6,10,33,11,70,64,75,80,60,180,69,58,43,31,32,44,30,无向网,有向网,7.1 图的定义和术语,稀疏图和稠密图 假设用n表示图中顶点数目，用e表示边或弧的数目。若不考虑顶点到其自身的弧或边，则对于无向图，边数e的取值范围是0到n(n-1)/2。称具有n(n-1)/2条边的无向图为完全图。对于有向图，弧的数目e的取值范围是0到n(n-1)。称具有n(n-1)条弧的有向图为有向完全图。若enlogn，则称为稀疏图，反之称为稠密图。子图 假设有两个图G=(V,E)和G=(V,E)，若V V且E E，则称G为G的子图。,7.1

5、图的定义和术语,度、入度和出度 若u-v是图中的一条弧，则称u邻接到v，或v邻接自u。图中所邻接到某顶点v的弧的数目，称为该顶点的入度，记作:ID(v)；反之，从某顶点u出发的弧的数目，称为该顶点的出度，记作:OD(u)。顶点v的入度和出度之和称为该顶点的总度，简称为度，记作:TD(v)。例如图G1中顶点B的入度ID(B)=2，出度OD(B)=3，度TD(B)=5。无向图中顶点的度定义为与该顶点相连的边的数目。一般情况下，如果顶点vi的度记作TD(vi)，则一个含有n个顶点，e条边或弧的图，满足如下关系：,7.1 图的定义和术语,路径和回路 若有向图G中k+1个顶点之间都有弧存在，则这个顶点的

6、序列v0,v1,vk为从顶点v0到顶点vk的一条有向路径，路径中弧的数目定义为路径长度。若序列中的顶点都不相同，则为简单路径。对无向图，相邻顶点之间存在边的k+1个顶点序列构成一条长度为k的无向路径。如若v0和vk是同一个顶点，则是一条由某个顶点出发又回到自身的路径，称这种路径为回路或环。,7.1 图的定义和术语,连通图和连通分量 若无向图中任意两个顶点之间都存在一条无向路径，则称该无向图为连通图。对有向图而言，若图中任意两个顶点之间都存在一条有向路径，则称该有向图为强连通图。非连通图中的各个极大连通子图称为该图的连通分量。,非强连通图和强连通分量,非连通图和连通分量,7.1 图的定义和术语,

7、图的抽象数据类型ADT Graph 数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。数据关系R:R=VR VR=|v,wP(v,w),表示从到的弧,谓词P(v,w)定义了弧的意义或信息 基本操作：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestoryGraph(&G)初始条件：图G存在。操作结果：销毁图G。LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。,more,7.1 图的定义和术语,GetVex(G,v

8、)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的值。PutVex(&G,v,value)初始条件：图G存在，v是G中的某个顶点。操作结果：对v赋值value。FirstAdjVex(G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的第一个邻接点，若该顶点在G中无邻接点，则返回空。NextAdjVex(G,v,w)初始条件：图G存在，v是G中的某个顶点，w是v的邻接顶点。操作结果：返回v的(相对于w的)下一个邻接点。若w是v的最后一个邻接点，则返回空。,more,7.1 图的定义和术语,InsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征。操作结果

9、：在图G中增添新顶点v。DeleteVex(&G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w)初始条件：图G存在，v和w是G中的两个顶点。操作结果：在图G中增添弧，若G是无向的，则还增添对称弧。DeleteArc(&G,v,w)初始条件：图G存在，v和w是G中的两个顶点。操作结果：在图G中删除弧，若G是无向的，则还删除对称弧。,more,7.1 图的定义和术语,DFSTraverse(G,v,visit()初始条件：图G存在，v是G中的某个顶点，visit是针对顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并对每个

10、顶点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。BFSTraverse(G,v,visit()初始条件：图G存在，v是G中的某个顶点，visit是针对顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。ADT Graph,7.2 图的存储结构,图是一种典型的复杂结构，图中顶点可能同任意一个其他顶点之间存在关系。因此，图没有顺序映象的存储结构。图有两种常用的存储结构。7.2.1 图的数组(邻接矩阵)存储表示 邻接矩阵是用于描述图中顶点之间的关系(及弧或边的权)的矩阵，假设图中顶点数为n，则邻

11、接矩阵A=(ai,j)m*n定义为：,Aij=,1 若Vi和Vj之间有弧或边存在,0 Vi和Vj之间没有弧或边存在,7.2.1 图的数组(邻接矩阵)存储表示,有向图G1,无向图G2,G1的邻接矩阵,G2的邻接矩阵,7.2.1 图的数组(邻接矩阵)存储表示,一般情况下，图中没有邻接到自身的弧，因此矩阵中主对角线全为零。由于无向图中一条边视为一对弧，则无向图的邻接矩阵必然是对称矩阵。网的邻接矩阵定义中，当vi到vj有弧相邻接时，ai,j的值为该弧上的权值，否则为。,7.2.1 图的数组(邻接矩阵)存储表示,有向图的邻接矩阵大多为稀疏矩阵，可以采用压缩存储表示。用二维数组表示更为方便，它和顶点信息等

12、其他图的信息一起构成图的一种存储表示const INFINITY_INT_MAX=MAX;/最大值设为MAXconst MAX_VERTEX_NUM=20;/最大顶点个数typedef enum DG,DN,AG,ANGraphKind;/图类型(有向图、有向网、无向图、无向网)typedef struct ArcCellVRType adj;/VRType为顶点的关系类型。对无权图，用1或0表示是否相邻；对带权图则为权值类型InfoType*info;/指向该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struc

13、tVertexType vexsMAX_VERTEX_NUM;/描述顶点的数组AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧(边)数GraphKind kind;/图的种类标志MGraph;,7.2.2图的邻接表存储表示,邻接表是图的一种链式存储表示方法，它类似于树的孩子链表。在有向图的邻接表中，从同一个顶点出发的弧链接在同一链表中，邻接表中结点的个数恰好为图中弧的个数。在无向图的邻接表中，同一条边有两个结点，分别出现在和它相关的两个顶点的链表中，因此无向图的邻接表中结点个数是边的两倍。,7.2.2图的邻接表存储表示,有向图G1,MAX_VER

14、TEX_NUM,7.2.2图的邻接表存储表示,MAX_VERTEX_NUM,无向图G2,7.2.2图的邻接表存储表示,邻接表定义如下：const MAX_VERTEX_NUM=20;typedef struct ArcNodeint adjvex;/该弧所指向的顶点的位置struct ArcNode*nextarc;/指向下一条弧的指针InfoType*info;/指向该弧相关信息的指针ArcNode;typedef struct VNodeVertexType data;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧VNode,AdjListMAX_VERTEX_NU

15、M;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志ALGraph;,算法7.1void CreateUDG(ALGraph/for/CreateUDG,7.3 图的遍历,与二叉树和树的遍历类似，图结构也有遍历操作，即从某个顶点出发，沿着某条路径对图中其余顶点进行访问，且使每一个顶点只被访问一次。但图的遍历要比树的遍历更复杂，因为图中和同一顶点有弧或边相通的顶点之间可能也有弧或边，那么在访问了某个顶点之后，可能沿着某条回路又回到了该顶点。为了避免同一顶点被重复访问，则在遍历过程中，必须为已经

16、访问过的顶点加上标识，以便再次途径这样的顶点时不再重复访问。为此，需附设一维数组visited0.n-1，令其每个分量对应图中一个顶点，各分量的初值均设为FALSE或0，一旦访问了某个顶点，便将visited中相应分量的值置为TRUE或被访问时的序号。通常，对图进行遍历可有两种搜索路径：深度优先搜索和广度优先搜索。,7.3.1 深度优先搜索遍历图,深度优先搜索遍历类似于树的先根遍历，可以看成是先根遍历的推广。假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到，若此时尚有其

17、他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。,7.3.1 深度优先搜索遍历图,例如，从v3出发对下图进行深度优先搜索，首先访问顶点v3，然后从v3的邻接顶点v2出发进行深度优先搜索，先后访问v4、v9和v1，由于v3的第二个邻接顶点v1已经被访问过，则不再从v1出发进行搜索，而v3的下一个邻接点v6未被访问，则再从v6出发进行搜索。,搜索过程中访问顶点的次序为：v3-v2-v4-v9-v1-v6-v5-v8-v7,7.3.1 深度优先搜索遍历图,算法7.2 Boolean visitMAX;void DF

18、STraverse(Graph G,Status(*Visit)(int v)VisitFunc=Visit;for(v=0;vG.vexnum;v+)visitv=False;for(v=0;vG.vexnum;v+)if(!visitv)DFS(G,v);void 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(!visitw)DFS(w);/对v的尚未访问的邻接顶点w递归调用DFS/DFS

19、FirstAdjVex(G,v)返回图G中顶点v的第一个邻接点，NextAdjVex(G,v,w)返回图G中v相对于w的下一个邻接点，w!=0说明尚有邻接点存在。,7.3.1 深度优先搜索遍历图,在实际应用中，首先要为图选定存储结构，假设采用邻接表表示图，则算法7.2具体化为算法7.3。算法7.3void DFS(ALGraph G,int v)/从第v个顶点出发递归地深度优先遍历图G visitv=TRUE;VisitFunc(G.verticesv.data);for(p=G.verticesv.firstarc;p;p=p-nextarc;)w=p-adjvex;if(!visitedw

20、)DFS(G,W);/对v未访问过的邻接顶点w递归调用DFS/for/DFS,7.3.1深度优先搜索遍历图,查找的顺序为：1、2、4、8、5、6、3、7,1,1,1,1,1,1,1,1,1,7.3.2 广度优先搜索遍历图,广度优先搜索的基本思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。换

21、句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2.的顶点。,7.3.2 广度优先搜索遍历图,例如，从v3开始对下图进行广度优先搜索遍历的过程为：首先访问v3和v3的邻接点v2、v1和v6，然后依次访问v2的邻接点v4和v6的邻接点v5，接着访问v4的邻接点v9，最后访问v5的邻接点v8和v7。由于这些顶点的邻接点都已经被访问，并且图中所有顶点都已被访问到，广度优先遍历至此结束。,一层,二层,三层,访问序列为：v3-v2-v1-v6-v4-v5-v9-v8-v7,7.3.2 广度优先搜索遍历图,可见，图的广度优先搜索过程类似于树的层次遍历。和深度优

22、先搜索类似，在遍历的过程中也需要借助于访问标志数组visited。并且为了实现按照顶点被访问的先后次序查询它们的邻接点，需附设一个队列依访问次序存储已被访问的顶点。对以邻接矩阵表示方法存储的图进行广度优先遍历的算法如7.5所示。,7.3.2 广度优先搜索遍历图,算法7.5void BFSTraverse(MGraph G)bool visitedG.vexnum;/附设访问标志数组 SqQueue Q;/附设循环队列Q for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueve(Q,G.vexnum);for(v=0;vG.vexnum;+v)if(!visit

23、edv)visitedv=TRUE;VisitFunc(G.vexv);/访问第v个顶点 EnQueue_Sq(Q,v);/v入队列 while(!QueueEmpty_Sq(Q)DeQueue_Sq(Q,u);/队头元素出队并置为u for(w=0;wG.vexnum;w+)if(G.arcsu,w.adj/当前访问的顶点w入队列Q/if/while/if/BFSTraverse,7.3.2 广度优先搜索遍历图,从以上几个算法中可以看出，遍历图的过程实质上是通过边或弧找邻接点的过程，其消耗时间取决于所采用的存储结构。因此若采用同样的存储结构，广度优先遍历的时间复杂度和深度优先搜索相同。由于算

24、法7.5中的存储结构为邻接矩阵，因此算法7.5的时间复杂度为O(n2)。图遍历是图的基本操作，也是一些图的应用问题求解算法的基础，以此为框架可以派生出许多应用算法。,7.4 图的连通性问题,7.4.1 无向图的连通分量和生成树 7.4.2 有向图的强连通分量 7.4.3 连通网的最小生成树,7.4.1 无向图的连通分量和生成树,对于连通图从任一顶点出发进行深度（广度）优先遍历，即可访问到图的所有顶点；对于非连通图需要从多个顶点出发进行遍历。,(a)非连通图,(b)非连通图的两个极大连通分量,7.4.1 无向图的连通分量和生成树,设连通图G边的集合为E(G)，将E(G)分为两个集合T(G)和B(

25、G)，T(G)为遍历图过程中经历的边的集合，B(G)为剩余的边。T(G)和G中所有顶点一起构成连通图G的极大连通子图，是连通图的生成树。如果遍历采用深度优先搜索，则得到的深度优先生成树；如果遍历采用广度优先搜索，则得到的广度优先生成树。而非连通图只有生成树林。,7.4.2 有向图的强连通分量,(a)非强连通图,(b)非强连通图两个强连通分量,在有向图G中，如果对于每一对vi,vjV，vi,vj，从vi到vj和从vj到vi都存在路径，则G是强连通图。有向图中的最大连通子图称作有向图的强连通分量。,7.4.3 连通网的最小生成树,在一个含有n个顶点的连通图中，必能从中选出n-1条边构成一个极小连通

26、子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边，称这棵树为连通图的生成树。例如，对下图(a)进行深度优先搜索遍历过程中经过的边和全部顶点构成的极小连通子图(b)即为(a)的一棵生成树。,(a),(b),7.4 连通网的最小生成树,在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。例如，对于如右图所示的连通网可以有多棵权值总和不相同的生成树。,(a)权值总和为43,(b)权值总和为36,(a)权值总和为64,权值序列：2 3 4 5 6 7 8 9 10 12 14 16,7.4 连通网的最小生

27、成树,构造连通网的最小生成树的算法主要有两种。1.克鲁斯卡尔(Kruskal)算法基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。,12,4,3,8,2,7,(c,e)产生回路,(c,f)产生回路,(f,g)产生回路,(b,c)产生回路,已选出n-1条边,7.4 连通网的最小生成树,2.普里姆(Prim)算法 假设G=(V,E)为一网，其中V为网中所有顶点的集合，E为网中所有带权边的集合。设置两个新的集合U和T，其中U用于存放G的

28、最小生成树中的顶点，T存放G的最小生成树中的边。令U的初值为U=u0(假设从顶点u0出发构造最小生成树)，令T的初值为空，T=。普里姆算法的思想是：从所有u?U，v?V-U的边中选取权值最小的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。,7.4 连通网的最小生成树,例如，利用Prim算法对下图从顶点a开始构造最小生成树。,a,b,c,d,e,f,g,U:a,T:,(a,b):12(a,f):16(a,g):14,12,U:a,b,T:(a,b),(a,f):16(a,g):14(b,c

29、):10(b,f):7,7,U:a,b,f,T:(a,b),(b,f),(a,g):14(b,c):10(f,c):6(f,e):2(f,g):9,2,U:a,b,e,f,T:(a,b),(b,f),(f,e),(a,g):14(b,c):10(e,c):5(e,d):4(e,g):8(f,c):6(f,g):9,4,U:a,b,d,e,f,T:(a,b),(b,f),(f,e),(e,d),(a,g):14(e,g):8(f,g):9(b,c):10(d,c):3(e,c):5(f,c):6,3,U:a,b,c,d,e,f,T:(a,b),(b,f),(f,e),(e,d),(d,c),(a

30、,g):14(e,g):8(f,g):9,8,U:a,b,c,d,e,f,g,T:(a,b),(b,f),(f,e),(e,d),(d,c),(e,g),此时，所有顶点都已加入集合U，即UV，最小生成树构造完毕。,7.4 连通网的最小生成树,比较以上两种算法可见：Kurskal算法主要对边进行操作，又称为“加边法”，其时间复杂度为O(e)。这种方法比较适用于稀疏图。Prim算法主要对顶点进行操作，又称为“加点法”，其时间复杂度为O(n2)。比较适用于稠密图。,7.5 有向无环图及其应用,一个无环的有向图称为有向无环图（directed acycline graph），简称DAG。,有向无环图是

31、描述一项系统或工程的进行过程的有效工具，常用来判断工程能否顺利进行及估算完成时间。,7.5.1 拓扑排序,有向无环图在工程计划和管理方面有着广泛的应用。一项工程往往可以分解为一些具有相对独立性的子工程，称这些子工程为活动。子工程之间在进行的时间上有着一定的相互制约关系。可以用有向图表示子工程及其相互制约关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为活动在顶点上的网络，简称活动顶点网络(Activity On Vertex Network)，或AOV网。,7.5.1 拓扑排序,什么是拓扑排序？若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。设R是

32、集合X上的偏序，如果对每个x,yX必有xRy或yRx，则称R是集合X上的全序关系。由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。,7.5.1 拓扑排序,例如，在课程计划中，每门课程的学习就是一项活动，一门课程可能以其他某几门课程为先修基础，而它本身又可能是另一些课程的先修基础，各课程之间的先修关系可用活动顶点网络表示。,7.5.1 拓扑排序,在活动网络中不允许出现回路，因为回路意味着某项活动的开始将以自己工作的完成为先决条件，这种情况称为死锁现象。检测有向图中是否存在回路的方法之一是求有向图中顶点的一个排列，这个排列满足：若在有向图中从u到v有一条弧，则在此序列中u一定排

33、在v之前，称有向图的这个操作为拓扑排序，所得顶点序列为拓扑有序序列。,7.5.1 拓扑排序,例如，下面两个序列就是左图的拓扑有序序列：C1,C9,C10,C13,C3,C11,C2,C4,C5,C6,C7,C8,C12C2,C4,C1,C9,C13,C3,C6,C5,C8,C7,C10,C11,C12通常，顶点的拓扑有序序列是不唯一的。但如果AOV网中存在回路，则不可能得到拓扑有序序列。,7.5.1 拓扑排序,如何进行拓扑排序？从其定义可知，在拓扑有序序列中的第一个顶点必定是在AOV网中没有前驱的结点，则首先在AOV网中选取一个没有前驱的顶点，输出它并从AOV网中删去所有以它为尾的弧，重复此操

34、作直至所有顶点都被输出为止。如果在此过程中找不到没有前驱的顶点，则说明尚未输出的子图中必有回路。,1,2,6,7,8,5,4,3,输出 2,2,输出 5,2 5,输出 7,2 5 7,输出 1,2 5 7 1,输出 3,2 5 7 1 3,输出 4,2 5 7 1 3 4,输出 6,2 5 7 1 3 4 6,输出 8,2 5 7 1 3 4 6 8,7.5.1 拓扑排序,在计算机中实拓扑排序算法时，需要以“入度为零”作为“没有前驱”的量度，而删除结点及以它为尾的弧的操作不必真正对图的存储结构进行，可用弧头顶点的入度减1来实现，算法如下所示：,建有向图的邻接表并统计各顶点的入度;取入度为0的顶

35、点v;while(v0)/尚有入度为零的顶点存在 cout0)/尚有V的邻接点存在 inDegreew-;/W的入度减一 w=nextAdj(v,w);/取V的下一个邻接点 取下一个入度为0的顶点v;if(mn)cout(“图中有回路”),7.5.2 关键路径,对于一项工程而言，还可以用弧表示活动，用顶点表示事件，所谓事件是一个关于某(几)项活动开始或完成的断言：指向它的弧所表示活动已经完成，从它出发的弧所表示的活动开始进行。每条弧可以带有权值，以表示活动进行需要的时间等。称这种网络为活动在边上的网络，简称为活动边网络，或AOE网。,如左图所示的AOE网，ai表示第i(i=1,2,11)项活动

36、，弧上的数字表示完成子工程所需要的天数。a表示整个工程的开始，其入度为零，通常称其为源点；k表示整个工程的结束，其出度为零，通常称其为汇点。一个工程的AOE网应该是一个单源点和单汇点的有向无环图。,7.5.2 关键路径,在AOE网络中，一条路径上各弧权值之和称为该路径的带权路径长度。由于AOE网络中某些活动可以并行进行，则完成整个工程的最短时间即为从源点到汇点最长的带权路径长度的值，称这样的路径为关键路径，关键路径上的弧称为关键活动。,例如，左图中从源点a到汇点k共有5条路径，带权路径长度如下：a-b-e-g-k:17a-b-e-h-k:18a-c-e-g-k:15a-c-e-h-k:16a-

37、d-f-h-k:15其中，a-b-e-h-k为关键路径a1,a4,a8,a11为关键活动,7.5.2 关键路径,如何求关键路径？首先定义四个描述量。假设顶点V1为源点，Vn为汇点，事件V1的发生时刻作为事件原点(0时刻)。,ve(j)：事件Vj可能发生的最早时刻，它是从V1到Vj的最长带权路径长度 0 j=1ve(j)=maxve(i)+w(ViVj)j=2,3,n Vi Vj 是弧 其中，w(ViVj)表示该弧的权值。对于一个特定的顶点Vj(2jn)，上式表示考察Vj的所有前驱结点Vi1，Vi2，Vip，在ve(i1)+w(Vi1Vj),ve(ip)+w(VipVj)中选最大值。计算ve时，

38、应该按顶点的拓扑有序次序从源点开始向下推算至汇点。,7.5.2 关键路径,vl(i)：在保证不延误整个工期，即保证Vn在ve(n)时刻发生的前提下，事件Vi发生所允许的最晚时刻。它等于ve(n)减去Vi到Vn的最长带权路径长度。ve(n)i=n vl(i)=minvl(j)-w(ViVj)i=n-1,2,1 ViVj是弧 对于一个特定的顶点Vi(1in-1)，上式考察Vi的所有后继结点Vj1，Vj2，Vjq，在vl(j1)-w(ViVj1),vl(jq)-w(ViVjq)中选最小值。计算vl时，顺序和ve相反，从汇点开始向回推算至源点。,7.5.2 关键路径,ee(k)：活动ak(令ak是Vi

39、Vj)可能开始的最早时刻。显然，它应该是事件Vi可能发生的最早时刻ve(i)，即ee(k)=ve(i)(k=1,2,m m为弧的数目)el(k)：活动ak(令ak是ViVj)在保证不延误整个工期的前提下，活动ak开始所允许的最晚时刻。它应该是Vj所发生所允许的最晚时刻vl(j)减去w(ViVj)，即：el(k)=vl(j)-w(ViVj)(k=1,2,m)根据ve和vl，可以计算出所有弧上的ee和el值，由ee(k)和el(k)的定义可知，如果某条弧ak的ee(k)和el(k)(1km)值相等，则为关键活动。反之，对于非关键活动，el(k)-ee(k)的值时该活动的期限余量(或称松弛时间)，在

40、此范围内的适度延误不会影响整个工程的工期。,7.5.2 关键路径,ve vl,ee el el-ee 权值,abcdefghk,a1a2a3a4a5a6a7a8a9a10a11,64511287424,从中可以看出，活动a1,a4,a8,a11为关键活动,7.5.2 关键路径,一个求解关键路径的AOE网,7.5.2 关键路径,ak由弧表示，设其持续时间为dut()，则：Ek=VEj;Lk=VLj-dut()求关键路径的步骤为：（1）从VE0=0开始递推求各顶点的最早发生时间：VEj=MAX(VEi+dut()(j=1.n-1)（2）从VLn-1=VLn-1开始递推求各顶点的最迟发生时间：VLi

41、=MIN(VLj-dut()(i=n-2.0)（3）计算各活动的最早开始时间和最迟开始时间，凡是差为0的均为关键活动。EEk=VEi;ELk=VLj-dut(),ak,EE5=4EL5=6,EE11=14EL11=14,EE7=7EL7=7,EE9=7EL9=10,EE1=0EL1=0,EE4=6EL4=6,EE2=0EL2=2,EE7=7EL7=7,EE10=16EL10=16,EE3=0EL3=3,EE6=5EL6=8,VL0=0,VL1=6,VL3=8,VL5=10,VL4=7,VL6=16,VL7=14,VL8=18,VL2=6,VE4=7,VE0=0,VE1=6,VE2=4,VE3=

42、5,VE5=7,VE6=16,VE7=14,VE8=18,7.6 单源最短路径,最短路径问题是图的典型应用问题。例如某一地区的一个公路网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，能否找到从某一城市A到另一城市B之间一条距离最近的通路呢？如果将城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，这个问题就归结为在有向网图中求顶点A到顶点B的所有路径中，边的权值之和最小的一条路径，这条路径就是两点之间的最短路径，并称路径上的第一个顶点为源点，最后一个顶点为终点。在非网图中最短路径是指两点之间经过的边数最少的路径。,7.6 单源最短路径,从源点到终点之间的路径可能存在三种情

43、况：没有路径相通只有一条路经，则此路径就是最短路径存在多条路径，则必存在一条最短路径,bf:没有路径 ba:只有一条路径 bd:存在三条路径(b-d):30(b-c-e-d):27(b-a-g-c-e-d):64其中，(b-c-e-d)为最短路径,7.6 单源最短路径,如何求得从源点到各终点的最短路径？Dijkstra提出了一种按路径长度递增的次序求从源点到各终点的最短路径的算法。假设从源点v0到各终点v1,v2,vk之间存在最短路径，其路径长度分别为l1,l2,lk，并且lp(1 从已求得的最短路径的顶点vp到该点有弧存在，且 和上的权值之和小于上的权值。依此类推，一般情况下，假设已求得最短

44、路径的顶点有vp1,vp2,vpk，则下一条最短路径的产生只可能是已求出的这些最短路径的延伸，也就是从源点间接到达终点，或者是从源点直接通过一条弧到达终点。,7.6 单源最短路径,根据以上思路，Dijkstra算法描述如下：1.假设ASnn为有向网的邻接矩阵，S为已找到最短路径的终点集合，其初始状态只含一个顶点，即源点。另设一维数组Distn，其中每个分量表示当前所找到的从源点出发(经过集合S中的顶点)到各个终点的最短路径长度，则Dist的初值为：Distk=ASi,k2.选择u，使得 Distu=minDistw|w V-S3.修改Dist数组中所有尚未找到最短路径的终点的对应分量值，如果

45、Distu+ASu,wDistw 则 Distw=Distu+ASu,w4.重复上述2和3的操作n-1次，即可求得从源点到所有终点的最短路径。此外，为了记下长度为Distw的最短路径，还需要附设路径矩阵Pathnn。,b,Dist7,Path77,S:bV-S:a,c,d,e,f,g,a b c d e f g,b,b,c,d,a,Dist和Path的初始状态，求得从b到c的最短路径,c,15,S:b,cV-S:a,d,e,f,g,b,g,c,d,b,b,e,c,e,e,修改Dist和Path的值，求得从b到e的最短路径,30,27,29,S:b,c,eV-S:a,d,f,g,修改Dist和Path的值，求得从b到a的最短路径,S:b,c,e,aV-S:d,f,g,修改Dist和Path的值，求得从b到d的最短路径,g,S:b,c,e,a,dV-S:f,g,修改Dist和Path的值，求得从b到g的最短路径,a,S:b,c,e,a,d,gV-S:f,修改Dist和Path的值，可见从b到f没有路径,至此，从源点b出发到各终点的最短路径求解完毕，最短路径序列如矩阵Path所示,abcdefg,abcdefg,a b c d e f g,