资源描述：
《数据结构拓扑排序和关键路径的求解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构课程设计大作业题目拓扑排序和关键路径的求解专业计算机科学与技术学生姓名学号指导教师完成日期2015.3哈尔滨理工大学目录一：实验内容概述2二：实验目的概述2三：解题思路的描述3四：源程序清单6五：程序调试及测试结果11六：结论13七：参考文献13拓扑排序和关键路径的求解【内容摘要】建立一个AOV网，把对象与对象之间的关系在AOV网中体现出来，要注意AOV网不可以建立成环的形式，否则工程将无法进行。之后对建立的网进行拓扑排序。对于一个工程来说，不仅要关心各子工程的之间的先后关系，还要关系整个工程的最短时间，即有向带权图的关键路径问题。在描述关键路径问题的有
2、向图时，顶点表示事件，便表示活动，边上的权表示活动所需的时间，即此有向图为AOE网。对AOV网构造其所有定点的线性序列，此序列保持网中各顶点间原有的先后关系，且是原来没有先后关系的顶点也成为有先后关系，这样的线性序列称为拓扑有序序列，构造AOV网的拓扑有序序列操作称为拓扑排序。在AOE网中有些活动可以并行地进行，所以完成整个工程的最短时间是从源点到汇点的最长路径的长度，路径长度是路径各边的权值之和，把从源点到汇点的最长路径称为关键路径。【关键字】AOE网拓扑排序关键路径Thetopologicalsortandcriticalpathmethod【Abstrac
3、t】EstablishaAOVnets,therelationshipbetweentheobjectandtheobjectinAOVnetsreflectedinAOVnets,shouldpayattentiontotheformofcan'testablishcyclization,otherwisetheprojectwillnotbeabletodoso.Afterthenetstoestablishtopologicalsort.Foraproject,itshouldnotonlyabouttherelationshipbetweenthecon
4、structionoftheproject,theshortesttimerelationship,whichisthekeytotheweightedgraphroutingproblem.Inthedescriptionofthecriticalpathproblemdigraph,vertices,thensaidthatevents,therightsideofthetimeneededtodenoteactivities,namely,thisistothenet.AOEForallitsdesignatedAOVnetworkstructure,th
5、esequenceoflinearsequenceofeachvertexkeeptherelationshipbetweentheoriginalandisoriginallyhasnosuccessivelyrelationshiphasbecomeavertex,suchaslineartopologicalorderlysequences,AOVtectonicsequencesoftopologicalorderlysequencesoperationcalledtopologicalsort.InsomeactivitycanAOEnetparall
6、eltocompletethewholeproject,sotheshortesttimefrompointoforigintothelengthofthelongestpathsinks,pathlengthisthepathtothesumoftheweights,fromthepointoforigintothelongestpathcalledzhonghuacriticalpath.【Keywords】AOEnetTopologicalsortThekeypath[在此处键入]一：实验内容概述采用图的邻接表（出边表）表示方法，实现拓扑排序和关键路径的求
7、解过程。使用实现的算法对于图的AOE网，求出各活动的可能的最早开始时间和最晚开始时间。输出整个工程的最短完成时间是多少？哪些活动是关键活动？说明哪项活动提高速度后能导致整个工程提前完成。二：实验目的概述AOE网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。在AOE网络中,有些活动顺序进行，有些活动并行进行。由于整个工程只有一个开始点和一个完成点，故在正常情况下（无环），网中只有一个入度为零的点（称作源点）和一个出度为零的点（叫做汇点）.如图1图1AOE网络在某些工程估算方面非常有用，为了进行人力、物力的调度和分配，以缩短工期，我们
8、必须找出影响工程进度的关
