201412203102016-毛伟-数据结构与算法作业-基于C语言的关键路径算法

数据结构与算法报告名称：基于C语言的关键路径算法作者：毛伟学号：201412203102016班级：计算机专升本2班学院：医学技术学院专业：计算机科学与技术指导老师：汤琼职务：2015年5月浙江.杭州摘要关键路径法（CriticalPathMethod，CPM），又称为要径法，是计划项目活动中用到的一种算术方法。对于有效的计划管理而言，关键路径是一个十分重要的工具。与AOV网相对应的是AOE-网（ActivityOnEdge）即边表示活动持续的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件（Event），弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。由于在AOE-网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各项活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径叫做关键路径（CriticalPath）。关键路径将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始-结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。要求实现图的关键路径，最小生成树，判断两点之间是否有路径，实现用C语言来编写代码，分析关键路径的目的提高效率。通过熟悉C语言的编程特点，了解数据结构对提高计算机的运行效率有非常大的帮助。关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。通过C语语言来实现关键路径的求解算法可以更加加深我们对数据结构与算法的理解，同时，也了解到关键路径是对拓扑排序的算法进行的修改。—关键词:关键路径AOE网算法C语言拓扑排序目录第一章概论.............................................................................................................................11.1报告背景............................................................................................................................11.2什么是关键路径................................................................................................................21.3关键路径法起源................................................................................................................31.4关键路径分类....................................................................................................................31.4.1箭线图....................................................................................................................41.4.2前导图....................................................................................................................51.5关键路径的特点................................................................................................................5第二章关键路径的意义...............................................................................................................62.1研究意义............................................................................................................................62.2关键路径的算法思想........................................................................................................62.3关键路径的算法................................................................................................................72.4关键路径的作用................................................................................................................7第三章关键路径的内容及核心算法...........................................................................................83.1关键路径的内容................................................................................................................83.2算法分析............................................................................................................................93.1核心算法..........................................................................................................................10参考文献.........................................................................................................................................11附录...........................................................................................................................................12C语言代码及运行截图..........................................................................................................121第一章概论1.1报告背景背景：了解到关键路径之前，先了解一下什么是图。图（Graph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后续；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子结点）相关，但只能和上一层中一个元素（即其双亲结点）相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。而关键路径法(CriticalPathMethod,CPM)是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种，属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在图中的数据元素通常称做顶点（Vertex），V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。若,vwVR，则,vw表示从v到w的一条弧（Arc），且称v为弧尾（Tail）或初始点（Initialnode），称w为弧头（Head）或终端点（Terminalnode），此时的图称为有向图（Digraph）。若,vwVR必有,wvVR即VR是对称的，则以无序对,vw代替这两个有序对，表示v和w之间的一条边（Edge），此时，的图称为无向图(Undigraph)。如下图所示：21.2什么是关键路径如图1所示是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2......，v9，每个事件表示在它之前的活动一完成，在它之后的活动可以开始。如v1表示整个工程的开始，v9表示整个工程结束，v5表示a4和a5已完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天。由于整个工程只有一个开始点和一个完成点，故在正常情况(无环)下，网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。那么该工程待研究的问题是：1.完成整项工程至少需要多少时间？2.哪些活动是影响工程进度的关键？由于在AOE-网中有些活动可以并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Criticalpath)。假设开始点是v1，从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候，也即是l(i)=e(i)的活动，我们称其为关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的功效，缩短整个工期。31.3关键路径法起源关键路径法（CPM）最早出现于1956年，当时美国杜邦（DuPont）公司拥有一台UNⅣAC1计算机，他们使用这台计算机进行他们公司几乎所有的数据处理工作，但是仍然还有大量的剩余时间，杜邦（DuPont）公司的管理层开始研究计算机在其它方面使用的可能性，因为当时电脑的费用是非常高昂的，他们考虑工程计划可能是应用电脑的一个方向。他们联系了雷明顿兰德（RemingtonRand）公司的Macuchy博士，帮他们解决计算机使用的问题，后者派出了年轻的数学家JamesE.Kelly去协助杜邦（DuPont）公司解决问题，杜邦公司方面的负责人是MorganWalker。他们要解决的问题是在工程项目中工期和费用之间的关系，他们研究的是如何能够采取正确的措