1、如何进行工如何进行工程设计使程设计使 工期最短工期最短？第第6 6章章 图图(5)(5).3.3 1 1、AOV-AOV-网网(1)(1)有向无环图有向无环图 概念概念：无环的有向图无环的有向图 应用：应用：工程流程、生产过程中各道工序的流程、程序流程、课工程流程、生产过程中各道工序的流程、程序流程、课程的流程等。程的流程等。(2)AOV-(2)AOV-网网 概念：概念：用用顶点顶点表示表示活动活动，弧弧表示活动间优先表示活动间优先关系关系的有向图称为的有向图称为顶点表示活动的网顶点表示活动的网(Activity On Vertex Network)(Activity On Vertex Ne
2、twork)简称为简称为AOV-AOV-网网。拓扑排序拓扑排序和和拓扑序列：拓扑序列：所谓所谓拓扑排序拓扑排序就是将就是将AOV-AOV-网中所有顶点网中所有顶点排成一个线性序列，该序列满足：若在排成一个线性序列，该序列满足：若在AOV-AOV-网中由顶点网中由顶点v vi i到顶点到顶点v vj j有一条路径，则在该线性序列中的顶点有一条路径，则在该线性序列中的顶点v vi i必定在顶点必定在顶点v vj j之前之前。该。该线线性序列性序列称为称为拓扑序列拓扑序列。课程关系例课程关系例 TKSTKS4 49:44 c4c1c2c3c12c9c10c11c6c7c8c5c1c1c2c2c3c3
3、c4c4c5c5c6c6c7c7c8c8c9c9c10c10c11c11c12c12程序设计程序设计离散数学离散数学数据结构数据结构汇编语言汇编语言算法分析算法分析计算机体系计算机体系编译方法编译方法操作系统操作系统高等数学高等数学线性代数线性代数电子电路电子电路数值分析数值分析无无 c1c1c1,c2c1,c2c1c1c3,c4c3,c4c11c11c5,c3c5,c3c3,c6c3,c6无无c9c9c9c9c9,c10,c1c9,c10,c1课程编号课程编号 课程名称课程名称 先决条件先决条件 某校计算机专业课程流程可用某校计算机专业课程流程可用AOVAOV网表示。其中网表示。其中顶点顶点
4、：表示：表示课课程程(也称活动也称活动)，弧弧：表示课程间的先修：表示课程间的先修关系关系；TKSTKS5 59:44 前驱和后继：前驱和后继：在网中，在网中，c4c1c2c3c12c9c10c11c6c7c8c5 右图的其中两个拓扑有序序列：右图的其中两个拓扑有序序列：(C(C1 1，C C2 2，C C3 3，C C4 4，C C5 5，C C7 7，C C9 9，C C1010，C C1111，C C6 6，C C1212，C C8 8)和和(C(C9 9，C C1010，C C1111，C C6 6，C C1 1，C C1212，C C4 4，C C2 2，C C3 3，C C5 5，
5、C C7 7，C C8 8)若从顶点若从顶点i i到顶点到顶点j j有一条有向路有一条有向路径，则径，则i i是是j j的前驱，的前驱，j j是是i i的后继。的后继。若从若从i i，j j点网中一条弧，则点网中一条弧，则i i是是j j的直接前驱，的直接前驱，j j点点i i的直接后继。的直接后继。AOV-AOV-网中不应出现有向环，检测网中不应出现有向环，检测的办法是对有向图构造其顶点的拓扑的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的有序序列，若网中所有顶点都在它的拓扑有序序列中，则该拓扑有序序列中，则该AOV-AOV-网中必不网中必不存在环。存在环。TKSTKS6 6
6、9:44(1)(1)(1)(1)示例示例c4c1c2c3c12c9c10c11c6c7c8c5 拓扑序列：拓扑序列：C C1 1C C9 9C C2 2C C4 4C C1010C C1111C C3 3C C1212C C6 6C C5 5C C8 8C C7 7TKSTKS7 79:44(1)(1)有关数据结构有关数据结构 顶点的入度：顶点的入度：intint degree degree 用于存储顶点的入度数用于存储顶点的入度数 整数栈整数栈 intint stack stack 用于存储入度为用于存储入度为0 0的顶点的编号的顶点的编号 整数组整数组 topotopo 用于记录拓扑序列的
7、顶点序号用于记录拓扑序列的顶点序号 邻接表中弧单链表结点结构邻接表中弧单链表结点结构 struct arcnodestruct arcnode int adjvex int adjvex;int int w;w;arcnode arcnode*nextarcnextarc;3 3、邻接表表头顶点数组元素结构邻接表表头顶点数组元素结构 typedef struct vnodetypedef struct vnode int int data;data;arcnode arcnode*firstarcfirstarc;*adjlistadjlist;有向图有向图(AOV(AOV网网)的邻接表结构的
8、邻接表结构 struct algraphstruct algraph adjlist adjlist vertices;vertices;int vexnum,arcnum int vexnum,arcnum;TKSTKS8 89:44(2)(2)算法思想算法思想 求出各顶点的入度存人数组求出各顶点的入度存人数组indegreeindegree中，并将人度为中，并将人度为0 0的顶点的顶点入栈。入栈。while(while(栈非空栈非空)将栈顶顶点将栈顶顶点v v弹出并输和弹出并输和保存在拓扑序列数组保存在拓扑序列数组topotopo中；中；将将v v的每条出边的每条出边v,u 终点终点u u
9、的入度减的入度减1 1，若，若u u的入度变为的入度变为0 0，则把则把u u推入栈；推入栈；若输出的顶点数少于若输出的顶点数少于AOV-AOV-网的顶点个数，则输出网的顶点个数，则输出“有回路有回路”；否则拓扑排序正常结束。否则拓扑排序正常结束。TKSTKS9 99:44(3)(3)算法描述算法描述 计算顶点入度数算法计算顶点入度数算法 void findindegree(algraph g,int void findindegree(algraph g,int*indegreeindegree)int i;arcnode int i;arcnode *p;p;for(i=0;ig.vexn
10、um;i+)indegreei for(i=0;ig.vexnum;i+)indegreei=0;=0;for(i=0;ig.vexnum;i for(i=0;inextarc for(p=g.verticesi.firstarc;p;p=p-nextarc)indegreep-adjvex indegreep-adjvex+;+;拓扑排序算法拓扑排序算法 int topologicalsort(algraph g,int topoint topologicalsort(algraph g,int topo)int int*indegree,i,k,mindegree,i,k,m;stack
11、s;arcnode stack s;arcnode *p;p;indegree=new intg.vexnum indegree=new intg.vexnum;initstack(&s,g initstack(&s,g););TKSTKS 10109:44 findindegree(g,indegree findindegree(g,indegree););/计算顶点的入度数计算顶点的入度数 for(i=0;ig.vexnum;i for(i=0;ig.vexnum;i+)+)if(!indegreei)push(&s,i if(!indegreei)push(&s,i););/入度数为入度
12、数为0 0的顶点入栈的顶点入栈 m=0;m=0;/记录输出的顶点个数记录输出的顶点个数 while(!stackempty(swhile(!stackempty(s)/存在入度数为存在入度数为0 0的顶点的顶点 pop(&s,&i pop(&s,&i););/输出存在入度数为输出存在入度数为0 0的顶点的顶点 coutg.verticesi.datacoutg.verticesi.data ;nextarc for(p=g.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex k=p-adjvex;/对应顶点的入度数减对应顶点的入度数减1 1 if(-inde
13、greek=0)push(&s,k if(-indegreek=0)push(&s,k););/入度为入度为0 0的顶点入栈的顶点入栈 if(mg.vexnum if(mg.vexnum)return 0;)return 0;/图中有环图中有环 return 1;return 1;/拓扑排序正常结束拓扑排序正常结束 TKSTKS 11119:44(4)(4)算法分析算法分析 求入度：求入度：(e)(e)建零入度栈：建零入度栈：(n)(n)while while中共进行：中共进行：(e)(e)时间复杂度为：时间复杂度为：(n+e)(n+e).4.4 关键路径关键路径1 1、AOE-AOE-网网(
14、1)(1)问题问题 v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 假设以有向网表示一个施工流程图，弧上的权值表示完成对应假设以有向网表示一个施工流程图，弧上的权值表示完成对应项子工程所需时间。项子工程所需时间。问：哪些子工程项是问：哪些子工程项是“关键工程关键工程”？即：哪些子工程项将即：哪些子工程项将影响影响整个工程的整个工程的完成期限完成期限的。的。问：估算完成整项工程至少需要问：估算完成整项工程至少需要多少时间多少时间？TKSTKS 12129:44 v5v5v1v1v
15、2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4源点源点汇点汇点(2)AOE(2)AOE网网 即 边 表 示 活 动 的 网即 边 表 示 活 动 的 网(Activity On Edge)(Activity On Edge)。AOEAOE网网是一个带权的有向无环是一个带权的有向无环图，其中顶点表示事件，图，其中顶点表示事件，弧表示活动，权表示活动弧表示活动，权表示活动的持续的时间。通常，的持续的时间。通常，AOEAOE网可用来估算工程的完成时间。由于整个工程只有一个开始点和一网可用来估算工程的完
16、成时间。由于整个工程只有一个开始点和一个完成点，故在正常的情况个完成点，故在正常的情况(无环无环)下，网中只有一个入度为零的点下，网中只有一个入度为零的点(称作称作源点源点)(3)(3)路径长度、关键路径和关键活动路径长度、关键路径和关键活动 一条路径各弧上的权值之和称为该路径的一条路径各弧上的权值之和称为该路径的带权路径长度带权路径长度(简称简称路路径长度径长度)和一个出度为零的点和一个出度为零的点(叫做叫做汇点汇点)。TKSTKS 13139:44 v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=
17、4a10=2a11=4源点源点汇点汇点 从从源点源点到到汇点汇点的的带权带权路径长度路径长度最长的路径称最长的路径称关关键路径键路径(Critical path)(Critical path)(4)(4)求关键路径分析求关键路径分析 设活动设活动a ai i由弧由弧 表示，其持续时间认为表示，其持续时间认为dut(k,jdut()，即为，即为弧弧 的权值的权值(w wk,ik,i)。求事件的最早发生时间求事件的最早发生时间ve(ive(i)：进入事件进入事件v vi i的每一活动都结束，的每一活动都结束，v vi i才可发生，所以才可发生，所以ve(ive(i)是从源是从源点到点到v vi i
18、的最长路径长度。的最长路径长度。可根据拓扑顺序可根据拓扑顺序从源点从源点开始开始向汇点向汇点递推。递推。从从ve(0)ve(0)0 0开始向前递推开始向前递推 ve(ive(i)MaxMaxve(k)+dut(k,ive(k)+dut()k,i TT，1in-11in-1 其中其中T T是所有以是所有以v vi i为头的弧的集合。为头的弧的集合。关键路径上的活动叫关键路径上的活动叫关键活动。关键活动。TKSTKS 14149:44 求事件的最迟发生时间求事件的最迟发生时间vl(ivl(i)：事件事件v vi i的发生不得延误的发生不得延误v vi i的每的每一后继事件的最迟发生时间。为一后继事
19、件的最迟发生时间。为了不拖延工期，了不拖延工期，v vi i的最迟发生时的最迟发生时间不得迟于其后继事件间不得迟于其后继事件v vk k的最迟的最迟发生时间减去活动发生时间减去活动 的持续的持续时间时间dut(i,kdut()。v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 求出求出ve(ive(i)后，可根据逆拓扑顺序后，可根据逆拓扑顺序从汇点从汇点开始开始向源点向源点递推，求出递推，求出vl(ivl(i)。为不延误工期，令汇点最迟发生时间等于汇点为不延误工期，令汇点最迟发生
20、时间等于汇点最早发生时间：最早发生时间：vl(n-l)=ve(n-lvl(n-l)=ve(n-l)vl(i vl(i)=)=MinMinvl(k)-vl(k)-dut(i,kdut()S,0in-2S,0in-2 其中，其中，S S是所有以是所有以v vi i为尾的弧的集合，为尾的弧的集合，dut(i,kdut()是弧是弧 的权值。的权值。TKSTKS 15159:44 求活动求活动a ai i=v=的最早开始时间的最早开始时间e(ie(i)：只有事件只有事件v vj j发生了，活动发生了，活动a ai i才能开始。所以，活动才能开始。所以，活动a ai i的最早的最早开始时间等于事件开始时间
21、等于事件v vj j的最早发生的最早发生时间时间ve(jve(j)，即，即:e(i)=ve(j e(i)=ve(j)v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 求活动求活动a ai i=v=的最晚开始时间的最晚开始时间l(il(i)：活动活动a ai i的开始时间需的开始时间需保证保证不延误事件不延误事件v vk k的最迟发生时间。所以的最迟发生时间。所以活动活动a ai i的最晚开始时间的最晚开始时间l(il(i)等于事件等于事件v vk k的最迟发生时间的最迟发生时间v
22、l(kvl(k)减去活减去活动动a ai i的持续时间的持续时间dut(j,kdut()，即：即：l(il(i)vl(kvl(k)dut(j,kdut()(5)(5)总结总结 显然显然 l(il(i)e(i)e(i)的活动叫作关键活动；的活动叫作关键活动；关键路径上的所有活动都是关键活动；关键路径上的所有活动都是关键活动；TKSTKS 16169:44 v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前这两个递推公式的计算必须
23、分别在拓扑有序和逆拓扑有序的前提下进行，提下进行，也就是说，也就是说，ve(i-1)ve(i-1)必须在必须在v vi i所有前驱的最早发生时间求得之后所有前驱的最早发生时间求得之后才能确定，才能确定，而而vl(i-1)vl(i-1)则必须在则必须在v vi i的所有后继的最迟发生时间求得之后才能的所有后继的最迟发生时间求得之后才能确定。确定。因此，可在拓扑排序的基础上计算因此，可在拓扑排序的基础上计算ve(i-1)ve(i-1)和和vl(i-1)vl(i-1)。辨别关键活动就是要找辨别关键活动就是要找e(ie(i)l(il(i)的活动。的活动。要求要求e(ie(i)和和l(il(i)首先应求
24、得首先应求得事件的最早发生时间事件的最早发生时间ve(ive(i)和最和最晚发生时间晚发生时间vl(ivl(i)。ve(i ve(i)MaxMaxve(k)+dut(k,ive(k)+dut()vl(i vl(i)MinMinvl(k)-vl(k)-dut(i,kdut()TKSTKS 17179:44 v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4(1)(1)对图中顶点进行拓扑排序，对图中顶点进行拓扑排序，在拓扑排序过程中按拓扑序列求在拓扑排序过程中按拓扑序列求出 每 个 事
25、 件 的 最 早 发 生 时 间出 每 个 事 件 的 最 早 发 生 时 间ve(ive(i)。(2)(2)按逆拓扑序列求出每个事件按逆拓扑序列求出每个事件的最迟发生时间的最迟发生时间vl(ivl(i)。2 2、关键路径求解的过程、关键路径求解的过程(3)(3)求出每个活动求出每个活动a ai i的最早开始时间的最早开始时间e(ie(i)(4)(4)求出每个活动求出每个活动a ai i的最晚开始时间的最晚开始时间l(il(i)。(5)(5)找出找出e(i)=l(ie(i)=l(i)的活动的活动a ai i，即为关键活动。由关键活动形成的，即为关键活动。由关键活动形成的由源点到汇点的每一条路径
26、就是关键路径，关键路径有可能不止一由源点到汇点的每一条路径就是关键路径，关键路径有可能不止一条。条。例例6.4 6.4 对图对图6.226.22所示的所示的AOE-AOE-网，计算关键路径。网，计算关键路径。TKSTKS 18189:44 ve(0)=ve(0)=0 0(1)ve(i(1)ve(i)和和vl(ivl(i)的计算的计算v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40181864577161414161078660vl(0)=minvl(1)-dut(),vl(2)
27、-dut(),vl(3)-dut()vl(0)=minvl(1)-dut(),vl(2)-dut(),vl(3)-dut()=min6-6,6-4,8-5=min6-6,6-4,8-5=0 0ve(1)=ve(0)+6=0+6=ve(1)=ve(0)+6=0+6=6 6ve(2)=ve(0)+4=0+4=ve(2)=ve(0)+4=0+4=4 4ve(3)=ve(0)+5=0+5=ve(3)=ve(0)+5=0+5=5 5ve(4)=maxve(1)+dut(),ve(ve(4)=maxve(1)+dut(),ve(2)+dut2)+dut()=max6+1,4+1=()=max6+1,4+1
28、=7 7ve(5)=ve(3)+dut()=5+2=ve(5)=ve(3)+dut()=5+2=7 7ve(6)=ve(4)+dut()=7+9=ve(6)=ve(4)+dut()=7+9=1616ve(7)=maxve(4)+dut(),ve(5)+dut()=max7+7,7+4=ve(7)=maxve(4)+dut(),ve(5)+dut()=max7+7,7+4=1414ve(8)=maxve(6)+dut(),ve(7)+dut()=max16+2,14+4=ve(8)=maxve(6)+dut(),ve(7)+dut()=max16+2,14+4=1818vl(8)=ve(8)=v
29、l(8)=ve(8)=1818 vl(7)=vl(8)-dut()=18-4=vl(7)=vl(8)-dut()=18-4=1414 vl(6)=vl(8)-dut()=18-2=vl(6)=vl(8)-dut()=18-2=1616 vl(5)=vl(7)-dut()=14-4=vl(5)=vl(7)-dut()=14-4=1010vl(4)=minvl(7)-dut(),vl(6)-dut()=min14-7,16-9=vl(4)=minvl(7)-dut(),vl(6)-dut()=min14-7,16-9=7 7vl(3)=vl(5)-dut()=10-2=vl(3)=vl(5)-du
30、t()=10-2=8 8vl(1)=vl(4)-dut()=7-1=vl(1)=vl(4)-dut()=7-1=6 6 vl(2)=vl(4)-dut()=7-1=vl(2)=vl(4)-dut()=7-1=6 6TKSTKS 19199:44 v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40181864577161414161078660活动活动 a1 1-21-2 a2 1-31-3 a3 1-41-4 a4 2-52-5 a5 3-53-5 a6 4-64-6 a7 5-
31、75-7 a8 5-85-8 a9 6-86-8 a10 7-97-9 a11 8-98-9e el ll-el-e(2)e(i(2)e(i)和和l(il(i)的计算的计算 各活动的各活动的a ai i的最早开始时的最早开始时间间e(i)e(i)和最晚开始时间和最晚开始时间l(il(i)计算如下。计算如下。v2v2v5v5v1v1v7v7v8v8v9v9a1=6a4=1 a7=9a8=7a10=2a11=401818671614141676从表中可看出从表中可看出 a a1 1，a a4 4，a a7 7，a a8 8，a a1010，a a1111是关键活动，并可画出有关是关键活动，并可画出
32、有关键活动所构成的键活动所构成的关键路径关键路径。TKS 20200 00 00 06 64 45 57 77 77 7161614140 00 02 23 36 66 68 87 77 71010161614142 23 30 02 23 30 00 03 30 00 0(3)(3)关键活动关键活动3 3、关键路径算法的实现、关键路径算法的实现(1)(1)辅助的数据结构辅助的数据结构 一一维数组维数组veivei：事件：事件v vi i的最早发生时间。的最早发生时间。一一维数组维数组vlivli：事件：事件vivi的最迟发生时间。的最迟发生时间。一一维数组维数组topoitopoi：记录拓扑
33、序列的顶点序号。：记录拓扑序列的顶点序号。(2)(2)算法思想算法思想 调用拓扑排序算法，使拓扑序列保存在调用拓扑排序算法，使拓扑序列保存在topotopo中中；将每个事件的最早发生时间将每个事件的最早发生时间veivei 初始化为初始化为0 0，veivei=0=0；根据根据topotopo中的值，按从前向后的拓扑次序依次求每个事件的最中的值，按从前向后的拓扑次序依次求每个事件的最早发生时间早发生时间vejvej。取得拓扑序列中的顶点序号取得拓扑序列中的顶点序号 k k，k=topoik=topoi；用指针用指针p p依次指向依次指向k k的每个邻接顶点，取得每个邻接顶点的序号的每个邻接顶点
34、，取得每个邻接顶点的序号j=p-adjvexj=p-adjvex，依次更新顶点，依次更新顶点j j的最早发生时间的最早发生时间vejvej：if(vejvek+pif(vejweight)-weight)vej=vek+pvej=vek+p-weight-weightv5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40181864577161414161078660TKSTKS 21219:44 将每个事件的最迟发生时间将每个事件的最迟发生时间vlivli 初初始化为始化为汇点汇点
35、的最早发生时间：的最早发生时间：vli=ven-lvli=ven-l 根据根据topotopo中的值，按从后向前的逆拓扑中的值，按从后向前的逆拓扑次序依次求每个事件的最迟发生时间次序依次求每个事件的最迟发生时间vlivli。v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40181864577161414161078660 取得拓扑序列中的顶点序号取得拓扑序列中的顶点序号k k，k=topoik=topoi；用指针用指针p p依次指向依次指向k k的每个邻接顶点，取得每个邻接顶点的
36、序号的每个邻接顶点，取得每个邻接顶点的序号j=p-adjvexj=p-adjvex，依次根据，依次根据k k的邻接点，更新的邻接点，更新k k的最迟发生时间：的最迟发生时间：if(vlkvlj-p-weight)vlk=vlj-pif(vlkvlj-p-weight)vlk=vlj-p-weight;-weight;从源点开始，对于每个顶点从源点开始，对于每个顶点i i，用指针，用指针p p依次指向依次指向i i的每个邻接的每个邻接顶点，取得每个邻接顶点的序号顶点，取得每个邻接顶点的序号j=p-adjvexj=p-adjvex，分别计算活动，分别计算活动 的最早和最迟开始时间的最早和最迟开始时
37、间e e和和l l：e=veie=vei ,l=vlj-pl=vlj-p-weight-weight；如果如果e=le=l，则活动，则活动 为关键活动，输出为关键活动，输出 。TKSTKS 22229:44 int criticalpath(algraphint criticalpath(algraph g)g)arcnode arcnode *p;p;int int*ve,ve,*vl,vl,*topo,i,j,k,n,dut,ee,eltopo,i,j,k,n,dut,ee,el;ve=new intg.vexnum ve=new intg.vexnum;vl=new intg.vexnu
38、m vl=new intg.vexnum;topo=new intg.vexnum topo=new intg.vexnum;if(!topologicalsort(g,topo if(!topologicalsort(g,topo)return 0;return 0;n=g.vexnum n=g.vexnum;for(i=0;in;i+)vei for(i=0;iadjvex;dutj=p-adjvex;dut=p-w;=p-w;if(vejvek+dut)vej=vek+dutif(vejnextarcp=p-nextarc;for(i=0;in;ifor(i=0;i=0;i-)=n-1;
39、i=0;i-)/按逆拓扑序列顺序求按逆拓扑序列顺序求vlvl k=topoik=topoi;p=g.verticesk.firstarcp=g.verticesk.firstarc;while(pwhile(p)j=p-adjvex;dut j=p-adjvex;dut=p-w;=p-w;if(vlkvlj-dut)vlk=vlj-dut if(vlkvlj-dut)vlk=vlj-dut;p=p-nextarc p=p-nextarc;printf(a e l l-e printf(a e l l-e););for(i=0;in;i+)vlifor(i=0;iadjvex j=p-adjve
40、x;ee=vei ee=vei;el=vlj-p el=vlj-p-w;-w;coutg.verticesi.data coutg.verticesi.data ,g.verticesj.data ,g.verticesj.data;printf(%4d%4d%5d,ee,el,el-ee);printf(%4d%4d%5d,ee,el,el-ee);if(ee=el)printf if(ee=el)printf(critical activity);(critical activity);getch();p=p-nextarc getch();p=p-nextarc;return 1;ret
41、urn 1;for(i=0;in;ifor(i=0;in;i+)+)/输出活动并判断关键活动输出活动并判断关键活动v5v5v1v1v2v2v3v3v4v4v6v6v7v7v8v8v9v9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40181864577161414161078660TKSTKS 26269:44(8)(8)算法分析算法分析 求求e(i)e(i)和和l(i)l(i)的时间复杂度均为的时间复杂度均为(e)(e)；输出关键路径的时间复杂度为输出关键路径的时间复杂度为(n+e)(n+e)；故算法的时间复杂度为故算法的时间复杂度为(n+e)(
42、n+e)。(9)(9)提高关键活动的速度对提早完成整个工程的制约因素提高关键活动的速度对提早完成整个工程的制约因素 非关键活动上升为关键活动非关键活动上升为关键活动 关键路径不止一条关键路径不止一条(10)(10)应用性很强应用性很强 如，如，19561956年美国杜邦公司为了协调公司内部业务部门的工作，年美国杜邦公司为了协调公司内部业务部门的工作，在兰德公司的协助下提出了关键路径法，并于在兰德公司的协助下提出了关键路径法，并于19571957年首先应用于一年首先应用于一个价值个价值10001000万美元的化工厂的建设工作，结果使工期比原计划缩短万美元的化工厂的建设工作，结果使工期比原计划缩短了了4 4个月时间，杜邦公司在采用关键路径法后的一年中就节省了个月时间，杜邦公司在采用关键路径法后的一年中就节省了100100万美元，取得了显著的效果。万美元，取得了显著的效果。？1 1、书面作业：、书面作业：P161P161：2 2中中(5)(5)2 2、实践：、实践：实验二、栈序列匹配实验二、栈序列匹配 TKSTKS 27279:44
