（精品课件）拓扑排序和关键路径.docVIP

7．5有向无环图及其应用 概念 一个无环的有向图称作为有向无环图。简称DAG图。 应用 描述含有公共子式的表达式的有效工具。 描述一项工程或系统的进行过程的有效工具。 （拓扑排序、关键路径） 7．5．1拓扑排序 用顶点表示活动，用弧表示活动间的优先关系的有向图，称为顶点表示活动的网。 如：有向图可表示一个工程的施工图、一个产品生产的流程图、程序的数据流图。 例：某工程系统，其子工程的进行要求的先决条件是： 子工程 先决条件 v1(程序设计基础) 无 v2(面向对象程序设计) v1 v3(离散数学) v1 v4(面向对象的数据结构) v3,v2 v5(汇编语言) v1 V6(编译原理) v4 二、AOV网中不允许出现回路。 如何检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。 三、何谓“拓扑排序”？ 对有向图进行如下操作: 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 将一个偏序排成一个全序序列。 以上图给出的图为例求出拓扑序列。 四· 如何进行拓扑排序？ 1、从有向图中选取一个没有前驱的顶点，并输出之; 2、从有向图中删去此顶点以及所有以它为尾的弧; 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。（有环） 没有前驱 -- 入度为零 删除顶点及以它为尾的弧-- 弧头顶点的入度减1 五、存储结构 在头结点中增设顶点的入度 设一栈（队列）暂存所有入度为0的顶点。 形式算法: 取入度为零的顶点v; 　 status TopologicalSort(Algraph G){ FindInDegree(G,indegree); InitStack(S); For (i=0;iG.vexnum,++i) If (!indegree[i]) Push(S,i); Count=0; while (!stackEmpty(S)){ POP(S,i); printf(i,G.vertices[i].data); ++count; for (p=G.vertices[i].firstarc;p;p=p-nextarc) {k=p-adjvex; If (!(--indegree[k])) Push(S,k); } } if (countG.vexnum) return ERROR; else return OK; } 7.5.2关键路径 AOE网 一个带权的有项无环图，边表示活动的网。 顶点表示事件，弧表示活动，权表示活动连续的时间。 通常，用来估算工程的完成时间。 a4=1 a7=9 a10=2 a1=6 a2=4 a8=7 a5=1 a11=4 a3=5 a9=4 a6=2 AOE网特点 一般情况下只有一个入度为0的顶点（源点、开始点） 一般情况下只有一个出度为0的顶点。（汇点、完成点） 3、关键路径：从源点到汇点存在有最长路径长度（权值之和最大）的路径。 4、关于某事件vj及其活动ai的四个时间值 a)事件vj的最早发生时间ve(j)----从源点开始到vj的最长路径长度。 他决定以vj开始的弧的最早发生时间。 如v5的ve(5)=7 b)活动ai的最迟开始时间L(i)-----不影响整个工程完成的前提下，活动ai最迟必须开始的时间。L(5)=6 事件vj的最迟发生事件Vl(j)-----发生事件vj的前一活动ai-1最迟的开始时间与前一个活动的持续时间dut之和. Vl(5)=6+1 活动ai的最早开始时间e(i)---由ve(j)决定。j是ai的起始点。e(i)=ve(j) e(7)=ve(5)=7 5、关键活动—完成活动ai的时间余量=l(i)-e(i)=0的活动。 6、结论 关键路径上所有的活动都是关键活动。 提前完成的非关键活动不能加快工程进度。 找出L(i)-e(i)=0的那些关键活动，设法提高工效，缩短工期。 7、求关键路径的算法原理 (1)先求ve(j)和vl(j) 设ai用j,k表示，其持续时间记为dut(j,k)则e(i)=ve(j) l(i)=vl(k)-dut(j,k) 求Ve(j):由源点向汇点推出 从ve(1)=0加上各个活动的持续时间，选取其最大者。得 ve(j)=max{ve(i)+dut(i,j)} 其中j相对固定，i在变。 (2=j=n) (为j所在直接前躯)