搜索
数据结构课程设计大作业题目拓扑排序和关键路径的求解专业计算机科学与技术学生姓名学号指导教师完成日期2015.3哈尔滨理工大学目录一：实验内容概述.......................................................................................................................................2二：实验目的概述.......................................................................................................................................2三：解题思路的描述...................................................................................................................................3四：源程序清单...........................................................................................................................................6五：程序调试及测试结果.........................................................................................................................11六：结论.....................................................................................................................................................13七：参考文献.............................................................................................................................................13[在此处键入]拓扑排序和关键路径的求解【内容摘要】建立一个AOV网，把对象与对象之间的关系在AOV网中体现出来，要注意AOV网不可以建立成环的形式，否则工程将无法进行。之后对建立的网进行拓扑排序。对于一个工程来说，不仅要关心各子工程的之间的先后关系，还要关系整个工程的最短时间，即有向带权图的关键路径问题。在描述关键路径问题的有向图时，顶点表示事件，便表示活动，边上的权表示活动所需的时间，即此有向图为AOE网。对AOV网构造其所有定点的线性序列，此序列保持网中各顶点间原有的先后关系，且是原来没有先后关系的顶点也成为有先后关系，这样的线性序列称为拓扑有序序列，构造AOV网的拓扑有序序列操作称为拓扑排序。在AOE网中有些活动可以并行地进行，所以完成整个工程的最短时间是从源点到汇点的最长路径的长度，路径长度是路径各边的权值之和，把从源点到汇点的最长路径称为关键路径。【关键字】AOE网拓扑排序关键路径Thetopologicalsortandcriticalpathmethod【Abstract】EstablishaAOVnets,therelationshipbetweentheobjectandtheobjectinAOVnetsreflectedinAOVnets,shouldpayattentiontotheformofcan'testablishcyclization,otherwisetheprojectwillnotbeabletodoso.Afterthenetstoestablishtopologicalsort.Foraproject,itshouldnotonlyabouttherelationshipbetweentheconstructionoftheproject,theshortesttimerelationship,whichisthekeytotheweightedgraphroutingproblem.Inthedescriptionofthecriticalpathproblemdigraph,vertices,thensaidthatevents,therightsideofthetimeneededtodenoteactivities,namely,thisistothenet.AOEForallitsdesignatedAOVnetworkstructure,thesequenceoflinearsequenceofeachvertexkeeptherelationshipbetweentheoriginalandisoriginallyhasnosuccessivelyrelationshiphasbecomeavertex,suchaslineartopologicalorderlysequences,AOVtectonicsequencesoftopologicalorderlysequencesoperationcalledtopologicalsort.InsomeactivitycanAOEnetparalleltocompletethewholeproject,sotheshortesttimefrompointoforigintothelengthofthelongestpathsinks,pathlengthisthepathtothesumoftheweights,fromthepointoforigintothelongestpathcalledzhonghuacriticalpath.【Keywords】AOEnetTopologicalsortThekeypath[在此处键入]一：实验内容概述采用图的邻接表（出边表）表示方法，实现拓扑排序和关键路径的求解过程。使用实现的算法对于图的AOE网，求出各活动的可能的最早开始时间和最晚开始时间。输出整个工程的最短完成时间是多少？哪些活动是关键活动？说明哪项活动提高速度后能导致整个工程提前完成。二：实验目的概述AOE网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。在AOE网络中,有些活动顺序进行，有些活动并行进行。由于整个工程只有一个开始点和一个完成点，故在正常情况下（无环），网中只有一个入度为零的点（称作源点）和一个出度为零的点（叫做汇点）.如图1图1AOE网络在某些工程估算方面非常有用，为了进行人力、物力的调度和分配，以缩短工期，我们必须找出影响工程进度的关键活动，争取提高关键活动的功效，若网中有多条关键路径那么只提高一条关键路径上的关键活动的速度还不能导致整个工程缩短工期，还必须提高同时在所有关键路径上的活动的速度，因此必须求出所有关键路径。[在此处键入]三：解题思路的描述从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。事件Vi的最早开始时间Ve(i)为源点V1到Vi的最长路径长度。活动ai的最早开始时间e(i)，活动ai的最迟开始时间l(i),e(i)=l(i)的活动叫做关键活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到。例如，下图是一个有11项活动的AOE-网。其中有9个事件V1,V2,…,V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如V1表示整个工程开始，V9表示整个工程结束，V5表示活动a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的数指的是执行该活动所需的时间。如，活动a1需要6天，活动a4需要1天等等。从源点到汇点的关键路径为：V1，V2，V5，V8，V9，路径长度为18，即活动V9的最早发生时间是18。活动a6的最早开始时间是5，最迟开始时间是8，这意味着：活动a6推迟3天开始或者延迟3天完成，都不会影响这个工程的完成。分析：①关键路径上的所有活动都是关键活动，只有提高关键活动的效率，才能缩短整个工期。②提前完成非关键活动并不能加快工程进度。③辨别关键活动就是找l(i)=e(i)的活动。④要得到活动的l(i)和e(i)，必须先计算事件的最早和最迟发生时间ve和vl。[在此处键入]关键路径举例找出图一中的关键路径！为了找出关键路径，需要找出关键活动；因此需要计算每个事件、每个活动的最早开始时间和最晚开始时间。最早开始时间需要从源点开始正向的进行计算，而最晚开始时间需要从汇点逆向的开始计算。（a）（b）（c）图二：[在此处键入]关键路径的算法：1．入e条弧〈j,k〉，建立AOE-网的存储结构；2．从源点V0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[I](1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。3．从汇点vn出发，令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[I](n-2≥i≥0)；4．根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s),则为关键活动。Statuscriticalpath(algraphg){//G为有向网，输出G的各项关键活动。If(!topologicalorder(G,t)returnERROR;Vl[0..G.vexnum-1]=ve[G.vexnum-1];//初始化顶点事件的最迟发生时间While(!stackempty(t))//按拓扑逆序求各项点的vl值For(pop(t,j),p=g.vextices[j].firstarc;p;p=p-nextarc){K=p-adjvex;dut=*(p-info);//dut〈j,k〉If(vl[k]-dutvl[j])vl[j]=vl[k]-dut;}for(j=0;jg.vexnum;++j)//求ee,el和关键活动for(p=g.vertices[j]).firstarc;p;p=p-nextarc){k=p-adjvex;dut=*(p-info);ee=ve[j];el=vl[k]-dut;tag=(ee==el)?’*’:”;printf(j,k,dut,ee,el,tag);//输出关键活动}}//criticalpath[在此处键入]四：源程序清单#includestdio.h#includestdlib.h#includeprocess.h#includectype.htypedefstructnode//边表结点类型{intadjvex;//顶点的序号intdut;//边上的权值structnode*next;//指向下一条边的指针}edgenode;typedefstruct//顶点表结点{intprojectname;//顶点域intid;//顶点入度edgenode*link;//边表头指针}vexnode;//建立图存储结构voidCreateGraphic(vexnode*Graph