《拓扑排序与关键路径课件.ppt》由会员分享，可在线阅读，更多相关《拓扑排序与关键路径课件.ppt（57页珍藏版）》请在三一办公上搜索。
1、有向无环图：一个无环的有向图，简称DAG图。P179 图7.22、7.23DAG图：描述含有公共子式的表达式及工程或系统的进行过程时的有效工具。活动：一个较大的工程被划分成许多子工程，这些子工程被称作活动。活动之间，存在某种约束，如：某些子工程的开始必须在另外一些子工程完成之后。关心问题：1.工程能否顺利进行2.估算 整个工程完成所必须的最短时间,7.5有向无环图及其应用拓扑排序问题提出：学生选修课程问题顶点表示课程有向弧表示先决条件，若课程i是j的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序定义AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称
2、为顶点表示活动的网(Activity On Vertex network)，简称AOV网若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动以自己为先决条件,拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止,拓扑序列：C1-C2-C3-C4
3、-C5-C7-C9-C10-C11-C6-C12-C8或：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一个AOV网的拓扑序列不是唯一的,算法实现以邻接表作存储结构设置一个包含n个元素的一维数组indegree，保存AOV网中每个顶点的入度值。把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1，即indegreek-1；若Vk的入度为0则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕,算法描述,1,6,输出序列：6,输出序列：6,输出序列：6,输出序列
4、：6,输出序列：6,输出序列：6,输出序列：6 1,输出序列：6 1,输出序列：6 1,4,输出序列：6 1,4,输出序列：6 1,4,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1 3,4,3,输出序列：6 1 3,4,输出序列：6 1 3,4,输出序列：6 1 3,4,输出序列：6 1 3,4,2,输出序列：6 1 3,4,2,输出序列：6 1 3,4,2,输出序列：6 1 3 2,4,2,输出序列：6 1 3 2,4,输出序列：6 1 3 2 4,4,输出序列：6 1 3 2 4,输出序列
5、：6 1 3 2 4,5,输出序列：6 1 3 2 4,5,输出序列：6 1 3 2 4 5,5,输出序列：6 1 3 2 4 5,算法分析-算法7.12,建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e),关键路径问题提出,把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始,例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？,定义AOE网(Activity On Edg
6、e)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间路径长度路径上各活动持续时间之和关键路径路径长度最长的路径叫Ve(j)表示事件Vj的最早发生时间Vl(j)表示事件Vj的最迟发生时间e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间l(i)-e(i)表示完成活动ai的时间余量关键活动关键路径上的活动叫，即l(i)=e(i)的活动,问题分析如何找e(i)=l(i)的关键活动？,设活动ai用弧表示，其持续时间记为：dut()则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,
7、(1)从Ve(1)=0开始递推,(2)从Vl(n)=Ve(n)开始递推,求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i),V1V2V3V4V5V6V7V8V9,064577161418,0668710161418,a1a2a3a4a5a6a7a8a9a10a11,算法实现以邻接表作存储结构从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Vei从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vli根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动,算法描述1-输入顶点和弧信息，建立其邻接表 计算每个顶点的入度2-对其进行拓扑排
8、序2.1-排序过程中求顶点的Vei2.2-将得到的拓扑序列进栈3-按逆拓扑序列求顶点的Vli4-计算每条弧的ei和li,找出ei=li的关键活动,Status TopologicalOrder(ALGraph G,Stack/TopologicalOrder,Status CriticalPath(ALGraph G)/算法7.14,G为有向网，输出G的各项关键活动。Stack T;int a,j,k,el,ee,dut;char tag;ArcNode*p;if(!TopologicalOrder(G,T)return ERROR;for(a=0;anextarc)k=p-adjvex;dut=p-info;/dut if(vlk-dut nextarc)k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*:;printf(j,k,dut,ee,el,tag);/输出关键活动 return OK;/CriticalPath,对图示的AOE 网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl(Vj)的函数值，列出各条关键路径。,
