数据结构——第7章图和广义表1.ppt

《数据结构——第7章图和广义表1.ppt》由会员分享，可在线阅读，更多相关《数据结构——第7章图和广义表1.ppt（57页珍藏版）》请在三一办公上搜索。

1、数据结构的内容,图的特点,顶点的前驱和后继个数无限制,图的应用,顶点之间的关系是任意的,图中任意两个顶点之间都可能相关,图（Graph）是一种非线性结构。,计算机科学,多对多,7.1 基本术语7.2 存储结构7.3 图的遍历7.4 连通网的最小生成树7.5 单源最短路径7.6 拓朴排序7.7 关键路径7.8 广义表,第7章 图和广义表,7.1 图的基本术语,图：记为 G(V,E)其中：V 是G的顶点集合，是有穷非空集；E 是G的边集合，是有穷集。,问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。,有向图：无向图：完全图：,图G中的每条边都是有方向的；图G中的每条边都是

2、无方向的；图G任意两个顶点都有一条边相连接；,若 n 个顶点的无向图有 n(n-1)/2 条边,称为无向完全图若 n 个顶点的有向图有n(n-1)条边,称为有向完全图,V=vertex E=edge,例：判断下列4种图形各属什么类型？,无向图,无向图(树),有向图,有向图,n(n-1)/2 条边,n(n-1)条边,完全图,完全图,设有两个图 G(V,E)和 G(V,E)。若 V V 且 E E,则称 图G 是 图G 的子图。,子 图：,带权图：,即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。,带权图（带权的有向图与无向图）,网 络：,顶点v的度是与它相关联的边的

3、条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点 v 的入度是以 v 为终点的有向边的条数,记作 ID(v);顶点 v 的出度是以 v 为始点的有向边的条数,记作 OD(v)。,问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,答：是树！而且是一棵有向树！,度入度出度,简单路径：,路径上各顶点 v1,v2,.,vm 均不互相重复。,回 路：,例：,若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。,路径：,在图 G(V,E)中,若从顶点 vi 出发,沿一些边经过一些顶点 vp1,vp2,vpm，到达顶点vj。则称顶点

4、序列(vi vp1 vp2.vpm vj)为从顶点vi 到顶点 vj 的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应当是属于E的边。,路径长度：,非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。,在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。,在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,强连通图：,连通图：,生成树：,是

5、一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。,生成森林：,由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,7.2 图的存储结构,图的特点：非线性结构（m:n）,邻接表邻接多重表十字链表,设计为邻接矩阵,链式存储结构：,顺序存储结构：,无！,（多个顶点，无序可言）但可用数组描述元素间关系。,可用多重链表,重点介绍：,邻接矩阵(数组)表示法邻接表(链式)表示法,7.2.1 邻接矩阵（数组）表示法,一个有 n 个顶点的图，可用两个数组存储。其中一个 一维数组存储数据元素（顶点）的信息，

6、另一个二维数组（邻接矩阵）存储数据元素之间的关系（边或弧）的信息。设图 G=(V,E)有 n 个顶点，则图的邻接矩阵是一个二维数组 A nn，定义为：,例1：,邻接矩阵：,A=,（v1 v2 v3 v4 v5）,v1v2v3v4v5,0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0,分析1：无向图的邻接矩阵是对称的；分析2：顶点i 的度第 i 行(列)中1 的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。,0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0,0 1 0 1 01 0 1 0 10 1 0

7、 1 11 0 1 0 10 1 1 1 0,顶点表：,例2：有向图的邻接矩阵,分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=A i j 顶点的入度=第i列元素之和。ID(Vi)=A j i 顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi),邻接矩阵：,A=,(v1 v2 v3 v4),v1v2v3v4,0 0 0 00 0 0 0 0 0 0 0 0 0 0 0,注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。,顶点表：,0 1 1 00 0 0

8、 0 0 0 0 1 1 0 0 0,0 1 1 00 0 0 0 0 0 0 1 1 0 0 0,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,特别讨论：网（即有权图）的邻接矩阵,以有向网为例：,邻接矩阵：,N=,(v1 v2 v3 v4 v5 v6),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：,5 7 4 8 9 5 6 5 3 1,5 7 4 8 9 5 6 5 3 1,图的数组（邻接矩阵）存储表示：,#define INFINITY INT_MAX/最大值#de

9、fine MAX_VERTEX_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 struct VertexType vexsMAX_VERTEX_NUM;/顶点向量 AdjMatrix arcs;/邻接矩阵

10、 int vexnum,arcnum;/图的当前顶点数和弧(边)数 GraphKind kind;/图的种类标志 MGraph;,7.2.2 图的邻接表存储表示法（链式存储）,头结点,表结点,3,1,4,2,0,4,3,1,2,0,2,1,特点：,若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头 结点和 2e 个表结点。适宜存储稀疏图。,无向图中顶点 vi 的度为第 i 个单链表中的结点数。,0,1,2,3,2,1,3,0,v1,v3,v4,v2,邻接表,逆邻接表,顶点 vi 的出度为第 i 个 单链表中的结点个数。,特点：,顶点 vi 的入度为整个单 链表中邻接点域值是 i-1 的

11、结点个数。,找出度易，找入度难。,找入度易，找出度难。,顶点 vi 的入度为第 i 个 单链表中的结点个数。,顶点 vi 的出度为整个单 链表中邻接点域值是 i-1 的结点个数。,图的邻接表存储表示：,#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 InfoType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc

12、;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志 ALGraph;,例1：无向图的邻接表,例2：有向图的邻接表,邻接表(出边),逆邻接表(入边),注：邻接表不唯一，因各个边结点的链入顺序是任意的。,邻接表,例3：已知某网的邻接（出边）表，请画出该网络。,当邻接表的存储结构形成后，图便唯一确定！,分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是

13、稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度？,邻接表的缺点：,怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：,需遍历全表,邻接表的优点：,TD(Vi)=单链表中链接的结点个数,OD(Vi)单链出边表中链接的结点数I D(Vi)邻接点为Vi的弧个数,TD(Vi)=OD(Vi)+I D(Vi),空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧

14、，需搜索两结点对应的单链表，没有邻接矩阵方便。,讨论：邻接表与邻接矩阵有什么异同之处？,【联系】邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。【区别】对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。【用途】邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),选择题 1.在一个图中，所有顶点的度数之和等于所有边数的()倍。（A）1/2（B）1（C）2（D）4 2.在一个有向图中，所有顶点的入度之和

15、等于所有顶点的出度之和的()倍。（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）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

16、 对于一个具有 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）后根遍历（C）按层遍历,一、深度优先搜索二、广度优先搜索,7.3 图的遍历,遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。,遍历实质：找每个顶点的邻接点的过程。图的特点：图

17、中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,解决思路：可设置一个辅助数组 visited n，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited i为1，防止它被多次访问。,图常用的遍历：,怎样避免重复访问？,7.3.1 深度优先遍历（DFS）（类似树的先根遍历）,方法：1、访问指定的起始顶点；2、若当前访问的顶点的邻接顶点有未被访问的，则任选 一个访问之；反之，退回到最近访问过的顶点；直到 与起始顶点相通的全部顶点都访问完毕；3、若此时图中尚有顶点未被访问，

18、则再选其中一个顶点 作为起始顶点并访问之，转 2；反之，遍历结束。,例：,V1,顶点访问次序：,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,连通图的深度优先遍历类似于树的先根遍历,a,b,c,h,d,e,k,f,g,a,c,h,d,f,k,e,b,g,顶点访问次序:,例：,a,c,h,d,f,k,e,g,b,a,c,h,f,k,e,d,b,g,解决办法：为每个顶点设立一个“访问标志”。,如何判别V的邻接点是

19、否被访问？,首先将图中每个顶点的访问标志设为 FALSE,之后搜索图 中每个顶点，如果未被访问，则以该顶点为起始点，进行深度 优先遍历，否则继续检查下一顶点。,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,0 1 2 3 4 5 6 7,2,V6,5,V7,6,4,1,1,1,1,1,1,1,1,7.3.2 广度优先遍历（BFS）（类似于树的按层遍历）,方法：从图的某一结点出发，首先依次访问该结点的所有邻 接顶点 Vi1,Vi2,Vin 再按这些顶点被访问的先后次序依次访问 与它们相邻接的所有未被访问的顶点，

20、重复此过程，直至所有顶 点均被访问为止。,例：,广度优先遍历：,V1,V2,V3,V4,V5,V6,V7,V8,V1,V3,V2,V7,V6,V5,V4,V8,V1,V2,V3,V5,V4,V7,V6,V8,a,b,c,h,d,e,k,f,g,a,c,d,e,f,h,k,b,g,顶点访问次序:,例：,a,c,d,e,f,h,k,g,b,1,3,4,0,V1,V2,V3,V4,V5,V6,实现：,0 1 2 3 4 5 6 7,V1 V2 V3 V4 V5 V6 V7 V8,0 1 2 3 4 5 6 7,2,V7,5,V8,6,7,1,1,1,1,1,1,1,1,7.4 连通网的最小生成树,1

21、.概念,生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,思考1：对连通图进行遍历，得到的是什么？得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的生成森林！,例1：画出下图的生成树,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,无向连通图,子图(或连通分量),生成森林,19,17,2 构造最小生成树,最小生成树

22、：给定一个无向网络，在该网的所有生成 树中，使得各边权数之和最小的那棵生成树称为该网的最 小生成树，也叫最小代价生成树。,要在 n 个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。,问题提出：,答案只能从生成树中找，因为要做到任何两个城市之 间有线路可达，通信网必须是连通的；但对长度最小的要求可以 知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连 通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。,希望找到一棵生成树，它的每条边上的权值之和（即建立 该通信网所需花费的总代价）最小 最小代价生成树。,问题分析：,结论：,讨论：如何求得

23、最小生成树？,有多种算法，但最常用的是以下两种：,最小生成树的 MST 性质如下：,Prim（普里姆）算法 Kruskal（克鲁斯卡尔）算法,Prime算法特点:将顶点归并，与边数无关，适于稠密网。Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。这两个算法，都是利用MST 性质来构造最小生成树的。,若U集是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0,v0)必在最小生成树上。,构造最小生成树方法：,方法一：普里姆(Prim)算法。,算法思想：,设 N=(V,E)是连通网，TE 是 N 上最小生成树中边的集合。,初始令 U=u0,(u0V)

24、,TE=。,在所有 uU,vV-U 的边(u,v)E 中，找一条代价最小的边(u0,v0)。,将(u0,v0)并入集合 TE，同时 v0 并入 U。,重复上述操作直至 U=V 为止，则 T=(V,TE)为 N 的最 小生成树。,V1,V3,V6,V4,V2,V5,例：,1,注：在最小生成树的生成过程中，所选的边都是 一端在V-U中，另一端在U中。,方法二：克鲁斯卡尔(Kruskal)算法。,V1,V6,V5,V4,V3,V2,6,5,1,3,5,6,6,4,2,5,算法思想：,设连通网 N=(V,E)，令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T=(V,)，每个顶点自成一个连通分

25、量。,在 E 中选取代价最小的边，若该边依附 的顶点落在 T 中不同的连通分量上（即：不能形成环），则将此边加入到 T 中；否 则，舍去此边，选取下一条代价最小的边。,依此类推，直至 T 中所有顶点都在同一 连通分量上为止。,5,V1,V6,V5,V4,V3,V2,1,5,2,3,4,5,N,T,最小生成树 可能不惟一,Kruskal（克鲁斯卡尔）算法,例：,例：应用克鲁斯卡尔算法构造最小生成树的过程,一顶点到其余各顶点,7.5.单源最短路径,两种常见的最短路径问题：一、单源最短路径用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径用Floyd（弗洛伊德）算法,典型用途：交通问题。如

26、：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。,（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）,任意两顶点之间,求单源最短路径(Dijkstra算法),目的：设一有向图G=（V,E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。,例1：,源点,从FA的路径有4条：FA：24 FBA：518=23 FBCA：5+7+9=21 FDCA：25+12+9

27、=36,又：从FB的最短路径是哪条？从FC的最短路径是哪条？,例：,讨论：计算机如何自动求出这些最短路径？,10,源点,终点,最,短,路,径,路径长度,30,100,60,50,90,70,60,01234,迪杰斯特拉(Dijkstra)算法：按路径长度递增次序产生最短路径,1、把 V 分成两组：(1)S：已求出最短路径的顶点的集合。(2)V-S=T：尚未确定最短路径的顶点集合。2、将 T 中顶点按最短路径递增的次序加入到 S 中，保证：(1)从源点 v0 到 S 中各顶点的最短路径长度都不大于 从 v0 到 T 中任何顶点的最短路径长度。(2)每个顶点对应一个距离值：S 中顶点：从 v0 到

28、此顶点的最短路 径长度。T 中顶点：从 v0 到此顶点的只包括 S 中顶点作中间顶点的 最短路径长度。,v5,v1,v6,v4,v3,v2,v0,8,5,6,2,30,13,7,17,32,9,Dijkstra 算法步骤：,T 中顶点对应的距离值用辅助数组 D 存放。,Di 初值：若 存在，则为其权值；否则为。,v2,1383032,v2,8,13133032,v3,v1,v1,13,13302220,v3,8+5,192220,v4,v4,8+5+6,2120,v6,v5,13+7,21,v5,v6,初始时令 S=v0,T=其余顶点。,v0,从 T 中选取一个其距离值最小的顶点 vj，加入

29、S。,对 T 中顶点的距离值进行修改：若加进 vj 作中间顶点，从 v0 到 vi 的距离值比 不加 vj 的路径要短，则修改此距离值。,重复上述步骤，直到 S=V 为止。,8+5+6+2,7.6 拓朴排序,AOV网(Activity On Vertices)用顶点表示活动的网络AOV网定义：若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系。Vi 必须先于活动Vj 进行。则这样的有向图叫做用顶点表示活动的网络，简称 AOV。AOE网(Activity On Edges)用边表示活动的网络AOE网定义：如果在无环的带权有向图中，用有向边表示一个工程中的活动，用边上权值表示活

30、动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称 AOE。,有两种常用的活动网络（Activity Network）：,AOV网络的用途：,我们经常用有向图来描述一个工程或系统的进行过程。一般来说，一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成。AOV网络若用于教学计划的制定，可以解决：哪些课程是必须先修的，哪些课程是可以并行学习的。,预备知识：拓扑排序,什么叫拓扑排序？,对一个有向无环图中的顶点排成一个具有前后次序的线性序列。,例：排课表。,C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,若 是网中有向边，则

31、i 是 j 的直接前驱；j 是 i 的直接后继。,AOV 网中不允许有回路，因为如 果有回路存在，则表明某项活动以 自己为先决条件，显然这是荒谬的。,问题：如何判别 AOV 网中是否存在回路？,C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,AOV 网的特点：,若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。,拓扑排序：,检测 AOV 网中是否存在环方法：对有向图构造其顶 点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序 列中，则该 AOV 网必定不存在环。,在 AOV 网没有回路的前提下，我们将全部 活动排列成一个线性序列，使得若

32、 AOV 网中有 弧 存在，则在这个序列中，i 一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序 序列，相应的拓扑有序排序的算法称为拓扑排序。,C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,拓扑排序的方法：,在有向图中选一个没有前驱的顶点且输出之。,从图中删除该顶点和所有以它为起点的弧。,重复上述两步，直至全部顶点均已输出；或者当图中 不存在无前驱的顶点为止。,C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8,拓扑序列：,C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8,一个AOV网的拓扑序列不是唯

33、一的,例：设一个工程有 11 项活 动，9 个事件。事件 v1 表示整个工程 开始（源点）事件 v9 表示整个工程 结束（汇点）,7.7 关键路径,把工程计划表示为有向图，用顶点表示事件，弧表示 活动，弧的权表示活动持续时间。每个事件表示在它之前 的活动已经完成，在它之后的活动可以开始。称这种有向 图为边表示活动的网，简称为 AOE(Activity On Edge)网。,对AOE网，我们关心两个问题：(1)完成整项工程至少需要 多少时间？(2)哪些活动是影响工程进 度的关键？,路径长度 路径上各活动持续时间之和。,关键路径 路径长度最长的路径。,ve(j)表示事件 vj 的最早发生时间。,v

34、l(j)表示事件 vj 的最迟发生时间。,e(i)表示活动 ai 的最早开始时间。,l(i)表示活动 ai 的最迟开始时间。,l(i)-e(i)表示完成活动 ai 的时间余量。,关键活动 关键路径上的活动，即 l(i)=e(i)的活动。,ve(3)=4,vl(3)=6,e(5)=4,l(5)=6,l(5)-e(5)=2,如何找 l(i)=e(i)的关键活动？,设活动 ai 用弧 表示，其持续时间记为：dut()则有：(1)e(i)=ve(j)(2)l(i)=vl(k)-dut(),(1)从 ve(1)=0 开始向前递推,(2)从 vl(n)=ve(n)开始向后递推,如何求 ve(j)和 vl(

35、j)？,求关键路径步骤：求 ve(i)、vl(j)求 e(i)、l(i)计算 l(i)-e(i),0 6 4 5 7 7161418,0 6 6 8 710161418,a11=4,1、若网中有几条关键 路径，则需加快同 时在几条关键路径 上的关键活动。如：a11、a10、a8、a7。,a8=7,a10=2,a7=9,a4=1,a1=6,a9=4,a5=1,a6=2,a2=4,v9,v6,v4,v3,a3=5,关键路径的讨论,2、如果一个活动处于所有的关键路径上，则提高这个活动 的速度，就能缩短整个工程的完成时间。如：a1、a4。,3、处于所有关键路径上的活动完成时间不能缩短太多，否 则会使原关键路径变成非关键路径。这时必须重新寻找 关键路径。如：a1由 6 天变成 3 天，就会改变关键路径。,v8,v7,v5,v2,v1,