[工学]山东科技大学数据结构课ppt7图.ppt

第1页 第2页 7.1 图的定义和术语 7.2 图的基本操作 7.3 图的存储结构 7.4 图的遍历 7.5 生成树和最小生成树 第3页 一 图的定义 图G由两个集合构成，记作G= 其中V是顶点的非空有限集合，E是 边的有限集合，其中边是顶点的无序对或有序对集合。 G1= V1=v0 ,v1,v2,v3,v4 E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4) 无序对(vi,vj)： 用连接顶点vi、vj的线段 表示，称为无向边； V0 V4 V3 V1 V2 例 G1 图示 第4页 G2 图示 有序对 ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧； V0 V1 V2 V3 G2= V2=v0 v1,v2,v3 E2= , , , 第5页 图的应用举例： 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 V0 V4 V3 V1 V2 V0 V1 V2 V3 第6页 二 图的基本术语 V0 V4 V3 V1 V2 V0 V1 V2 V3 1)无向图（undigraph）：在图G中，若所有边是无向边，则 称G为无向图； 2)有向图（digraph）：在图G中，若所有边是有向边，则称G 为有向图； 混和图：在图G中，即有无向边也有有向边，则称G为混合 图； 3)无向完全图：任意两顶点间都有边的图称为无向完全图。 在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 4）有向完全图：任意两顶点之间都有方向互为相反的两条弧 相连接的有向图称为有向完全图。在一个含有n个顶点的有向 完全图中，有n(n-1)条弧。 5）稠密图/稀疏图：若边数为e，顶点数为n，边数稀少到 eE (i=1,2,k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径； 若v=u，则称该序列为回路； 在图1中，V0,V1,V2,V3 是V0到V3的路径； V0,V1,V2,V3,V0是回路； 在图2中，V0,V2,V3 是V0到V3的路径； V0,V2,V3,V0是回路； 无向图G1 有向图G2 V0 V4 V3 V1 V2 V0 V1 V2 V3 例 第9页 10)简单路径和简单回路 在一条路径中,若除起点和终点外,所有顶点各不相同,则 称该路径为简单路径； 由简单路径组成的回路称为简单回路； 在图1中，V0,V1,V2,V3 是简单路径； V0,V1,V2,V4,V1 不是简单路径；在图2中， V0,V2,V3,V0是简单回路； 7.1 图的定义和术语 无向图G1 有向图G2 V0 V4 V3 V1 V2 V0 V1 V2 V3 例 第10页 11）子图 设有两个图G=（V，E）、G1=（V1，E1），若V1 V， E1 E，E1关联的顶点都在V1中，则称 G1是G的子图； 例 (b)、(c) 是 (a) 的子图 (a)(b) (c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 第11页 12）连通图（强连通图） 在无（有）向图G=中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图） 非连通图 连通图 强连通图 非强连通图 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4 第12页 13）连通分图（强连通分量） 无向图G 的极大连通子图称为G的连通分量 极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中 的顶点加入，子图不再连通； 连通分图 非连通图 V0 V2 V3 V1 V5 V4 V0 V2 V1 非连通分图 第13页 有向图D 的极大强连通子图称为D 的强连通分量 极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图 中的顶点加入，子图不再是强连通的； 强连通分量 V0 V1 V2 V3 V0 V2 V3 V1 7.1 图的定义和术语 第14页 14) 生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树 极小连通子图意思是：该子图是G 的连通子图，在该子图中删除任何一 条边，子图不再连通， 若T是G 的生成树当且仅当T 满足如下条件 T是G 的连通子图 T包含G 的所有顶点 T中无回路 连通图 G1 G1的生成树 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 第15页 生成树：极小连通子图，它含有图中全部全部顶 点，但是只有足以构成一棵树的n-1条边。 一棵有n个顶点的生成树有且仅有n-1条边。 无法将图中顶点排列成一个唯一的线性序列，任 何一个顶点都可被看成是第一个顶点。任一个顶 点的邻接点之间也不存在次序关系。 第16页 图有以下基本操作： 1）CreatGraph（G）：输入图G的顶点和边，建立 图G的存储。 2）DFSTraverse（G,V）：从图G的一个顶点V出 发深度优先遍历图G。 3）BFSTraverse（G,V）：从图G的一个顶点V出 发广度优先遍历图G。 第17页 图的存储结构至少要保存两类信息： 1)顶点的数据 2)顶点间的关系 约定: G=是图, V=v0,v1,v2, vn-1 ,设顶点的 角标为它的编号 如何表示顶点间的关系？ 顶点的编号 V0 V4 V3 V1 V2 V0 V1 V2 V3 第18页 1 邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵： Aij= 1 若(vi,vi+1)E 或 E 0 否则 0 1 0 1 0 10 1 0 1 0 1 0 1 1 10 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 10 0 0 一 邻接矩阵表示 V0 V4 V3 V1 V2 V0 V1 V2 V3 7.3 图的存储表示 第19页 无向图邻接矩阵表示法特点： 1）无向图邻接矩阵是对称矩阵，同一条边表示了两次； 2）顶点v的度：等于二维数组对应行（或列）中1的个数； 3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1； 4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0； 5）设图的顶点数为 n ,存储图用一维数组, 数组元素有 m 个 （m=n),则 G占用存储空间：m+n2；G占用存储空间只与它的顶点数有关，与边数无关；适 用于边稠密的图； 对有向图的数组表示法可做类似的讨论 0 1 0 1 0 10 1 0 1 0 1 0 1 1 10 1 0 0 0 1 1 0 0 邻接矩阵表示法的空间代价 只与图的顶点数有关 V0 V4 V3 V1 V2 7.3 图的存储表示 第20页 图的基本操作： 1）求无向图某顶点vi的度(或有向图中vi的出度)。Ai0到 Ain-1中的非0个数，即数组A中第i 行的非0 元素的个数； 2）求有向图某顶点vi 的 入度。： A0i到A n-1i 中的非0个数，即数 组A中第i 列的非0 元素的个数； 3）检测图中的总边数。扫描整个数组A，统计出数组中非0元素的个数。无向 图的总边数为非0元素个数的一半，而有向图的总弧数为非0元素个数； V0 V4 V3 V1 V2 V0 V1 V2 V3 0 1 0 1 0 10 1 0 1 0 1 0 1 1 10 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 10 0 0 第21页 邻接矩阵表示法对求顶点的度很方便。 在无向图中：顶点的度数=矩阵中对应该顶点 的行或列中非零元素的个数。 在有向图中： 顶点的出度=矩阵中对应该顶点的行中非零元 素的个数。 顶点的入度=矩阵中对应该顶点的列中非零元 素的个数。 第22页 V1V3 V2V4 V1V3 V2V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0 入度 出度 1 1 1 1 2 1 0 1 度数 3 2 1 2 第23页 V1V3 V2V4 V1 V2 V3 V4 V1 2 V2 8 V3 9 6 V4 4 2 8 4 6 网及其邻接矩阵 9 便于找一个图中某个顶点的邻接点序列 第24页 二邻接表 邻接表是图的链式存储结构：即对图中每个顶点建立一个单链表，第i个 单链表中的结点表示依附于该顶点Vi的边（或弧） 1 无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边 ：用线性链表存储 该结点表示边 （Vi Vj）,其中的1是Vj 在一维数组中的位置 例 V0 V4 V3 V1 V2 2 0 1 2 3 4 m-1 V0 V1 V2 V3 V4 13 4 2 2 1 1 0 0 3 4 下标 编号 link 第25页 图的邻接表类型定义 struct node /边（弧）结点的类型定义 int vertex; /边（弧）的另一顶点的在数组中的位置 struct node *link; /指向下一条边（弧）结点的指针 ; typedef struct NODE； NODE adjlistMAX; / 邻接点链表的头指针所对应的 数组 7.3 图的存储表示 第26页 无向图的邻接表的特点 1）在G邻接表中，同一条边对应两个结点； 2）顶点v的度：等于v对应线性链表的长度； 3）判定两顶点v ，u是否邻接：要看v对应线性链表中有无对应的结点 4）在G中增减边：要在两个单链表插入、删除结点； 5）设存储顶点的一维数组大小为m(m图的顶点数n), 图的边数为e，G占 用存储空间为：m+2*e。G占用存储空间与 G 的顶点数、边数均有关；适用 于边稀疏的图 0 1 2 3 4 m-1 V0 V1 V2 V3 V4 13 4 2 2 1 1 0 04 3 邻接表的空间代价 与图的边及顶点数均有关 V0 V4 V3 V1 V2 2 第27页 2 有向图的邻接表和逆邻接表 1）有向图的邻接表 顶点：用一维数组存储（按编号顺序） 以同一顶点为起点的弧：用线性链表存储 类似于无向图的邻接表， 所不同的是： 以同一顶点为起点的弧： 用线性链表存储 下标 编号 link V0 V1 V2 V3 12 3 0 0 1 2 3 m-1 例 V0 V1 V2 V3 第28页 2）有向图的逆邻接表 顶点：用一维数组存储（按编号顺序） 以同一顶点为终点的弧：用线性链表存储 V0 V1 V2 V3 0 1 2 3 m-1 0 0 2 3 类似于有向图的邻接表， 所不同的是： 以同一顶点为终点弧： 用线性链表存储 例 V0 V1 V2 V3 第29页 建立邻接表的算法 建立无向邻接表 int create(NODE *adjlist ) NODE *p; int num, i, v1, v2; scanf(“%dn”, /读入结点数 for(i=0; ivertex=v2; p-link=adjlistv1.link; adjlistv1.link=p; /插入在链表首部 p=(NODE *)malloc(sizeof(NODE); p-vertex=v1; p-link=adjlistv2.link; adjlistv2.link=p; return(num); / 返回图的结点数 第31页 （3）十字链表 V1V2 V3V4 0 1v 1 v 2 v 3 v 4 0 1 2 3 0 2 2 0 2 3 3 0 3 1 3 2 tailvexheadvexhlinktlinkinfo datafirstinfirstout 第32页 弧头相同的弧在同一链表上，弧尾相同的弧在同 一链表上。 十字链表也可以看成是邻接矩阵的链表存储结构 。 第33页 （4）邻接多重表 V1V3 V2V4 1 2 3 4 2 1 1 1 3 4 4 2 邻接表 第34页 V1V2 V4V5 v1 v2 v3 v4 v5 3 4 2 1 20 0 V3 0 1 2 3 421 431 v1 v2 v3 v4 v5 01 0 1 2 3 4 0 3 2123 41 2 4 mark 顶点 位置 下一 邻边 第35页 邻接多重表中，所有依附于同一顶点的边串联在 同一链表中。由于每条边依附于两个顶点，则每 个边结点同时链接在两个链表中。 与邻接表的区别： 用来表示同一条边的结点个数不同。 在存储量问题上，存储容量大致相同。 第36页 在不同的存储结构下，实现各 种操作的效率可能是不同的。所 以在求解实际问题时，要根据求 解问题所需操作，选择合适的存 储结构。 第37页 图的遍历：从图的某顶点出发，访问图中所有顶点，并且 每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其 他边回到已被访问过的顶点。为保证每一个顶点只被访问一次， 必须对顶点进行标记，一般用一个辅助数组 visitMAX作为对 顶点的标记，当顶点vi未被访问，visiti值为0；当vi已被访 问，则visiti值为1。 图的遍历与 树的遍历有什么不同 有两种遍历方法（它们对无向图，有向图都适用） 深度优先遍历 广度优先遍历 第38页 一 、深度优先遍历 从图中某顶点v出发： 1）访问顶点v； 2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；直至图 中所有和v有路径相通的顶点都被访问到； 3）若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始 点，重复上述过程。直至图中所有顶点都被访问到。 V0,V1,V3,V7,V4,V2,V 5,V6, 由于没有规定 访问邻接点的顺序， 深度优先序列不是唯一的 这是序列（1） 在遍历过程中 所经过的路径 例 求图G以V0起点的的深度优先序列： V0,V1,V4,V7,V3,V2,V5,V6 V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2 V7 V6 V5 V4 第39页 如果将图顶点的邻接点 看作二叉树结点的左、右孩子 深度优先遍历与先序遍历 是不是很类似？ 深度优先遍历 从图中某顶点v出发： （1）访问顶点v； （2）依次从v的未被访问的邻接点 出发，对图进行深度优先遍历； 先序遍历（DLR） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； V0 V7 V6 V5 V4 V3 V2 V1 第40页 结点定义 typedef struct node int vertex; / 边（弧）的另一顶点在数组中的位置 struct node *link; / 指向下一条边（弧）结点的指针 ; typedef struct NODE； NODE adjlistMAX; / 邻接点链表的头指针所对应的数组 辅助数组 int visitMAX; /顶点标志数组,全局变量 NODE * ptrMAX; /顶点链表指针数组 visit 0 1 2 3 4 m-1 0 0 0 0 0 深度优先遍历算法 第41页 void depthfirst( NODE adjlist, int num) int i; for (i=0; ivertex; 取结点的邻接顶点w if ( visitw= =0; ) dfs(w); ptrv=ptrv-link; / 记住顶点v 的邻接顶点位置， 该邻接点在w之后 从第v个顶点出发，递归地深度优先遍历图G 。 第43页 调用深度优先遍历算法的主函数 main( ) NODE adjlist MAX; int num; num=create(adjlist ); /* 建立图G 的邻接表 */ depthfirst(adjlist, num); /* 调用对图G 深度优先搜索算法*/ 深度优先遍历算法 第44页 V0 V7 V6 V5 V4 V3 V2 V1 0 1 2 3 4 5 6 7 V0 V1 V2 V3 V4 V5 V6 V7 12 0 1 1 5 7 7 30 6 4 26 52 43 第45页 如果将图顶点的邻接点 看作二叉树结点的左、右孩子 深度优先遍历算法与 先序遍历算法 的结构是不是很像？ 深度优先遍历算法 void dfs( int v) int w; printf( “%d, “, v); visitv=1; / 访问此结点 while (ptrv！=NULL） w= ptrv-vertex; 取结点的邻接顶点w if ( visitw= =0; ) dfs(w); ptrv=ptrv-link; / 记住顶点v 的邻接点位置， 该邻接点在w之后 先序遍历递归算法 void prev (NODE *root) if (root!=NULL) printf(“%d,”, root-data)； / 访问此结点 prev(root-lch); / 访问孩子结点 prev(root-rch); 比较 第46页 图中某未访问过的顶点vi出发： 1）访问顶点vi ； 2）访问 vi 的所有未被访问的邻接点w1 ,w2 , wk ； 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； 二、广度优先遍历（类似于树的按层遍历） V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2 V7 V6 V5 V4 这是序列（1） 在遍历过程中 所经过的路径 由于没有规定 访问邻接点的顺序， 广度优先序列不是唯一的 例 求图G 的以V0起点的的广度优先序列: V0,V1,V2,V3,V4,V5,V6,V7 第47页 从图中某顶点vi出发： 1）访问顶点vi ；（容易实现） 2）访问vi 的所有未被访问的邻接点w1 ,w2 , wk ； （容易实现） 3）依次从这些邻接点（在步骤 2）访问的顶点）出发，访问它们的所有 未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被 访问； 为实现 3），需要保存在步骤(2）中访问的顶点，而且访问这些顶点邻接 点的顺序为：先保存的顶点，其邻接点先被访问。 广度优先遍历算法 在广度优先遍历算法中， 需设置一队列Q， 保存已访问的顶点， 并控制遍历顶点的顺序。 V0 V7 V6 V5 V4 V3 V2 V1 第48页 广度优先遍历从图中某顶点v出发： 1）访问顶点v ； 2）访问v的所有未被访问的邻接点w1 ,w2 , wk ； 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接 点; 依此类推，直到图中所有访问过的顶点的邻接点都 被访问； V0 V7 V6 V5 V4 V3 V2 V1Q V1V2V3V0V4V5V6V7 V0V1V2V3V4V5V6V7 7.4 图的遍历 第49页 在广度优先遍历算法中， 需设置一队列 Q， 保存已访问的顶点， 并控制遍历顶点的顺序 int visitMAX; int queueMAX, front=0, rear=0; 第50页 void bft(int v) /从v出发，广度优先遍历图G。 int w; NODE *p; visitv=1;printf(“%d,”,v); enter(v); / enter(v)为入队列函数 while(v=leave()!=NULL); / leave()为出队列函数 p=adjlistv.link; /p指向出队列顶点v的第一个邻接点 while(p!=NULL) w = p-vertex; /遍历v所指的整个链表 if(visitw= =0) /如果w 未被访问过 printf(“%d,”,w); / 访问 w visitw=1;enter(w); 访问后，w 入队 p=p-link; 第51页 main( ) int num; num=create(adjlist); breadfirst(num); / 调用对图G 广度遍历图算法 void breadfirst(int num) int; for (i=0;i,则 表示活动i必须先于活动j进行。这种图称做顶点 表示活动的网络(Activity On Vertex network,简 称AOV网络)。 例如某校计算机专业的课程及其相互之间的关系 ，它对应的AOV网络如下页图所示。 * 第七章 图 83 第84页 * 第七章 图 84 第85页 * 第七章 图 85 第86页 在AOV网络中，如果顶点Vi的活动必须在顶点Vj 的活动以前进行，则称Vi为Vj的前趋顶点，而称 Vj为Vi的后继顶点。这种前趋后继关系有传递性 。 AOV网络中一定不能有有向环路。例如在下页 图那样的有向环路中，V2是V3的前趋顶点，V1 是V2的前趋顶点，V3又是V1的前趋顶点，环路 表示顶点之间的先后关系进入了死循环。 因此，对给定的AOV网络首先要判定网络中是 否存在环路，只有有向无环路网络在应用中才有 实际意义。 一个无环的有向图称为有向无环图，它是一类较 有向树更一般的特殊有向树。 * 第七章 图 86 第87页 * 第七章 图 87 第88页 所谓“拓扑排序”就是将AOV网络中的各个顶点( 各个活动)排列成一个线性有序序列，使得所有 要求的前趋、后继关系都能得到满足。 由于AOV网络中有些顶点之间没有次序要求，它 们在拓扑有序序列中的位置可以任意颠倒，所以 拓扑排序的结果一般并不是唯一的。 通过拓扑排序还可以判断出此AOV网络是否包含 有有向环路，若有向图G所有顶点都在拓扑排序 序列中，则AOV网络必定不包含有有向环路。 * 第七章 图 88 第89页 q(1) 在网络中选择一个没有前趋(入度为0)的顶点 ，并把它输出； q(2) 从网络中删去该顶点和从该顶点发出的所有 有向边； q(3) 重复执行上述两步，直到网中所有的顶点都 被输出 (此时，原AOV网络中的所有顶点和边就 都被删除掉了)。 q如果进行到某一步，无法找到无前趋的顶点，则 说明此AOV网络中存在有向环路，遇到这种情况 ，拓扑排序就无法进行了。 * 第七章 图 89 第90页 AOV网络 * 第七章 图 90 输出V3后 第91页 输出V4后 * 第七章 图 91 输出V2后 输出V1后 输出V5后 输出拓扑序列为：3 4 2 1 5 第92页 关键路径法是采用边表示活动(Activity On Edge)的网络，简称为AOE网络。 AOE网络是一个带权的有向无环路图，其中，每 个顶点代表一个事件(Event)，事件说明某些活动 或某一项活动的完成，即阶段性的结果。 离开某顶点的各条边所代表的活动，只有在该顶 点对应的事件出现后才能开始。 权值表示活动持续的时间。 * 第七章 图 92 第93页 * 第七章 图 93 第94页 通常利用AOE网络可以研究以下两个问题： (1) 完成整个工程至少需要多少时间？ (2) 哪些活动是影响工程进度的关键？ * 第七章 图 94 第95页 v完成工程所需的时间就是从开始点起进行到结束 点止所需的时间。 v路径长度是指沿路径各边的权值之和，也就是这 些边所代表的活动所需时间之和。 v完成整个工程所需的时间取决于从开始点到结束 点的最长路径长度，此长度最大的路径叫做关键 路径。 v分析关键路径的目的是辨别哪些是关键活动，以 便争取提高关键活动的效率，缩短整个工期。 * 第七章 图 95 第96页 在描述关键路径的算法时，设活动ai由弧表 示，要确定如下几个相关的量： (1) 事件Vj的最早出现时间和活动的最早开始时间 ：从源点V1到某顶点Vj的最长路径长度叫作事件j 的最早出现时间，表示成vej。顶点Vj的最早出现 时间 vej决定了从Vj指出的各条边所代表活动的 最早开始时间，因为事件j不出现，它后面的各项 活动就不能开始。我们以ei表示活动ai的最早开 始时间。显然ei= vej 。 * 第七章 图 96 第97页 q(2) 活动ai的最迟开始时间：在不影响整个工程按 时完成的前提下，此项活动最迟的必须开始时间， 表示成Li。 q只要某活动ai有Li=ei的关系，我们就称ai为关键 活动。关键活动只允许在一个确定的时间开始，再 早，它前面的事件还没出现，尚不能开始；再晚， 又会延误整个工程的按时完成。由于完成整个工程 所需的时间是由关键路径上各边权值之和所决定的 ，显然关键路径上各条边所对应的活动都是关键活 动。 * 第七章 图 97 第98页 (3) 事件j的最迟出现时间：即事件j在不延误整个 工程的前提下允许发生的最迟时间，表示为vlj。 对某条指向顶点Vk的边所代表的活动ai可得到： Li= vlk-(活动ai所需时间) 也就是活动ai必须先于它后面事件的最迟出现时间 开始，提前的时间为进行此活动所需的时间。 下图所示为活动开始时间与事件出现时间的关系 。 * 第七章 图 98 Vj ai Vk 第99页 v确定关键路径的方法就是要确定ei=Li的关键活 动。 v假设以wj,k表示有向边的权，即此边对应的 活动所需的时间，为了求AOE网络中活动ai的最早 开始时间ei和活动ai的最迟开始时间Li，先要求 得顶点Vk的最早出现时间vek和最迟出现时间 vlk 。 * 第七章 图 99 第100页 vek和vlk可以采用下面的递推公式计算： (1) 向汇点递推 由源点的ve1=0开始，利用公式： 向汇点的方向递推，可逐个求出各顶点的ve 。式 中p表示所有指向顶点的边的集合。 * 第七章 图 100 第101页 此式的意义为：从指向顶点Vk的各边的活动中取最 晚完成的一个活动的完成时间作为Vk的最早出现时 间vek。 * 第七章 图 101 第102页 (2) 向源点递推 由上一步的递推，最后总可求出汇点的最早出现时 间ven。因汇点就是结束点，最迟出现时间与最 早出现时间相同，即vln=ven。从汇点的最迟 出现时间vln开始，利用下面公式： 向源点的方向往回递推，可逐个求出各顶点的最迟 出现时间vl。式中s表示所有由Vj点指出的边的集 合，如下页图所示。 * 第七章 图 102 第103页 上述公式的意义为：由从Vj顶点指出的各边所 代表的活动中取需最早开始的一个开始时间作 为Vj的最迟出现时间。 * 第七章 图 103 第104页 无论是向汇点递推还是向源点递推，都必须按 一定的顶点顺序进行。 对所有的有向边，向汇点递推是先求出尾顶点 的ve值，再求头顶点的ve值；向源点递推则相 反，先求头顶点的vl值，再求尾顶点的vl值。 为此，可利用上节介绍的拓扑排序得到的顶点 次序进行向汇点的递推，向源点的递推按相反 的顺序进行即可，不必再重新排序。 * 第七章 图 104 第105页 * 第七章 图 105 第106页 由表可知时间余量为零的活动都是关键活动，即 为a1，a4，a7，a8，a10，a11。 这些关键活动构成两条关键路径，即关键路径 (V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9) 。 在安排工程时，对于关键活动和余量小的活动应 重点保证，余量较大的活动可适当地放松些，对 非关键活动加速进行，并不能使整个工程提前完 成，只有提高关键路径上的活动的效率，才能缩 短整个工程的工期。 * 第七章 图 106 第107页 v所谓最短路径（shortest path）问题指的是：如 果从图中某顶点出发（此点称为源点），经图的 边到达另一顶点（称为终点）的路径不止一条， 如何找到一条路径使沿此路径上各边的权值之和 为最小。 v设一有向网络G =（V,E），已知各边的权值，并 设每边的权均大于零，以某指定V0为源点，求从 V0到图的其余各点的最短路径。 v以下页图为例，若指定以顶点V6为源点V0，该图 比较简单，通过观察可