数据结构第28讲--关键路径--2018

数据结构中的关键路径算法解析关键路径算法是一种用于确定项目关键路径的方法，它可以帮助我们找到项目中耗时最长的路径，从而可以合理地安排任务和资源，提高项目完成的效率。

在数据结构中，关键路径算法也有着重要的应用。

本文将对数据结构中的关键路径算法进行解析和讨论。

一、什么是关键路径算法？关键路径算法是一种基于网络图的分析工具，它通过构建工程项目的网络模型，确定项目中的关键路径，以便更好地控制和管理项目进度。

关键路径是指项目中最长时间的路径，这条路径上的每个任务都是不能延误的，否则将会对整个项目的完成时间产生直接影响。

二、关键路径算法的基本步骤1. 创建网络图：将项目的任务和其所需的时间以及任务之间的依赖关系表示为有向无环图（DAG），其中顶点表示任务，边表示任务之间的依赖关系。

2. 计算任务的最早开始时间（ES）和最迟开始时间（LS）：从图的起点开始，依次计算每个任务的最早开始时间，即该任务能够开始执行的最早时间；然后从图的终点开始，逆序计算每个任务的最迟开始时间，即该任务必须在何时开始以保证项目能够按时完成。

3. 计算任务的最早完成时间（EF）和最迟完成时间（LF）：根据任务的最早开始时间和所需时间计算出任务的最早完成时间，即该任务能够完成的最早时间；然后根据任务的最迟开始时间和所需时间计算出任务的最迟完成时间，即该任务必须在何时完成以保证项目能够按时完成。

4. 计算任务的总时差（TF）：总时差等于任务的最迟完成时间减去最早完成时间，表示任务可以延误的时间。

5. 确定关键路径：根据任务的总时差，将总时差为零的任务连接起来，形成关键路径。

三、关键路径算法的实例为了更好地理解关键路径算法的应用，我们以一个简单的工程项目为例进行说明。

假设有以下任务需要完成：任务A：7天任务B：5天任务C：10天任务D：6天任务E：3天任务F：8天任务之间的依赖关系如下所示：A ->B -> D -> FA -> C -> E -> F首先，我们可以根据这些任务和依赖关系创建一个有向无环图（DAG），然后按照上述算法的步骤进行计算。

数据结构习题解答信息工程学院徐燕萍第1章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。

二、学习要点1．熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。

分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2．了解抽象数据类型的定义、表示和实现方法。

3．熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。

4．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。

5．掌握计算语句频度和估算算法时间复杂度的方法。

三、基础知识题1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

答：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示（又称映像）。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。

数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

程序设计语言中的数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

而抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。

这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。

n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。

即无向连通图的生成树不是唯一的。

连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。

图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。

最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。

最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。

解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。

他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。

时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。

数据结构关键路径 如果在有向⽆环图中⽤有向边表⽰⼀个⼯程中的各项活动（Activity），⽤有向边上的权值表⽰活动的持续时间（duration），⽤顶点表⽰事件（Event），则这种有向图叫做⽤边表⽰活动的⽹络（activity on edges），简称AOE⽹络。

例如： 其中，E i表⽰事件，a k表⽰活动。

E0是源点，E8是汇点。

完成整个⼯程所需的时间等于从源点到汇点的最长路径长度，即该路径中所有活动的持续时间之和最⼤。

这条路径称为关键路径（critical path）。

关键路径上所有活动都是关键活动。

所谓关键活动（critical activity），是不按期完成会影响整个⼯程进度的活动。

只要找到关键活动，就可以找到关键路径。

与计算关键活动有关的量： 1 事件E i的最早可能开始时间：Ee[i]—从源点E0到顶点E i的最长路径长度。

在上图中，Ee[4]=7。

2 事件E i的最迟允许开始时间：El(⼩写L)[i]—在保证汇点E n-1最迟允许开始时间El[n-1]等于整个⼯程所需时间的前提下，等于El[n-1]减去从E i到E n-1的最长路径长度。

3 活动a k的最早可能开始时间：e[k]—设该活动在有向边<E i，E j>上，从源点E0到顶点E i的最长路径长度，即等于Ee[i]。

4 活动a k的最迟允许开始时间：l(⼩写L)[k]—设该活动在有向边<E i，E j>上，在不会引起时间延误的前提下，允许的最迟开始时间。

l[k]=El[j]-dur(<E i，E j>)，其中dur(<E i，E j>)是完成该活动所需的时间，即有向边<E i，E j>的权值。

l[k]-e[k]表⽰活动a k的最早可能开始时间和最迟允许开始时间的时间余量，也叫做松弛时间（slack time）。

没有时间余量的活动是关键活动。

算法步骤： 1 输⼊顶点数和边数，再输⼊每条边的起点编号、终点编号和权值。

数据结构关键路径数据结构是计算机科学中非常重要的一门学科，它主要研究数据之间的组织方式和操作方法。

在计算机程序中，数据结构的选择和设计对程序的性能和效率有着重要的影响。

在数据结构中，关键路径是一个关键概念，它指的是一个任务完成所需要的最长时间。

1. 什么是关键路径在项目管理中，关键路径是指在一个项目的所有任务中，完成项目所需要的最长时间路径。

这条路径上的任务是项目完成的关键，如果其中任何一个任务延迟，整个项目的进度都会受到影响。

在数据结构中，关键路径指的是在一个算法或操作中，完成所需的最长时间。

它是算法或操作的瓶颈，决定了整个操作的效率。

2. 关键路径的计算方法计算关键路径的方法主要有两种：事件法和任务法。

事件法是一种图论的方法，通过绘制和分析项目的网络图来确定关键路径。

任务法是一种优化方法，通过对任务进行排序和计算来确定关键路径。

在数据结构中，计算关键路径通常是通过分析算法的复杂度来完成的。

算法的复杂度可以分为时间复杂度和空间复杂度，其中时间复杂度是计算算法执行所需的时间，空间复杂度是计算算法执行所需的空间。

通过分析算法的复杂度，可以确定算法的关键路径。

3. 关键路径的应用关键路径在数据结构中有着广泛的应用。

在算法设计中，关键路径可以帮助程序员找到算法的瓶颈并进行优化。

通过优化关键路径上的操作，可以提高算法的效率和性能。

此外，关键路径还可以应用于网络流量分析、图像处理、数据压缩等领域。

在网络流量分析中，关键路径可以帮助分析网络中的瓶颈和拥堵点，从而优化网络结构和提高传输效率。

在图像处理中，关键路径可以帮助找到图像处理的关键步骤，从而提高图像处理的速度和质量。

在数据压缩中，关键路径可以帮助找到数据压缩的关键操作，从而提高数据的压缩比例。

4. 关键路径的挑战尽管关键路径在数据结构中有着广泛的应用，但它也面临一些挑战。

首先，计算关键路径的过程通常是复杂且耗时的，需要对算法进行详细的分析和计算。

其次，关键路径可能随着算法或操作的不同而变化，需要根据具体情况进行调整和优化。

数据结构课程设计——关键路径《数据结构》课程设计报告课程题目：关键路径学院：班级：学号：姓名：指导教师：完成日期：目录一、需求分析 (2)二、概要设计 (4)三、详细设计 (5)四、调试分析 (12)五、用户使用说明 (13)六、测试结果 (14)七、附录 (14)一、需求分析1、问题描述AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。

它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。

2、设计步骤（1）、以某一工程为蓝本，采用图的结构表示实际的工程计划时间。

（2）、调查并分析和预测这个工程计划每个阶段的时间。

（3）、用调查的结果建立AOE网，并用图的形式表示。

（4 ）、用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。

（5）、用SearchMaxPath()函数求出最大路径，并打印出关键路径。

（6）、编写代码并调试、测试通过。

3、测试数据○v2○v5○v1○v4○○v36v1 v2 v3 v4 v5 v68v1 v2 a1 3v1 v3 a2 2v2 v4 a3 2v2 v5 a4 3 v3 v4 a5 4v3 v6 a6 3v4 v6 a7 2v5 v6 a8 1二、概要设计为了实现上述函数功能：1、抽象数据类型图的定义如下：ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={ VR }；VR={＜v，w＞|v，w∈V，且P(v，w)，＜v，w＞表示从v到w的弧，谓词P(v，w)定义了弧＜v，w＞的意义和信息 }基本操作：InitGraph(G);初始条件：图G存在。

数据结构课程设计报告题目：关键路径算法院（系）：计算机工程学院专业：计算机科学与技术班级：嵌入式1091学生：吕帅指导教师：寇海洲孙成富邱军林殷路2010年12月目录一、设计目的 (3)二、设计内容 (3)三、程序设计步骤 (4)四、调试分析 (12)五、测试结果 (12)六、课程设计小结 (16)一、设计目的1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。

2、提高程序设计和调试能力。

学生通过上机实习，验证自己设计的算法的正确性。

学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。

4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。

二、设计内容1、系统名称：关键路径算法AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。

它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。

2、要求：1 以某一工程为蓝本，采用图的结构表示实际的工程计划时间。

2 调查并分析和预测这个工程计划每个阶段的时间。

3 用调查的结果建立AOE网，并用图的形式表示。

4 用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。

5 用SearchMaxPath()函数求出最大路径，并打印出关键路径。

关键路径若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续时间），则此带权的有向图称为边表示活动的网(Activity on Edge Network) ，简称AOE 网。

【例】图7.21 是一个网。

其中有9 个事件v 1 , v 2 , … , v 9 ；11 项活动 a 1 , a 2 , … , a 11 。

每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。

如v 1 表示整个工程开始，v 9 表示整个工程结束。

V 5 表示活动a 4 和a 5 已经完成，活动a 7 和a 8 可以开始。

与每个活动相联系的权表示完成该活动所需的时间。

如活动 a 1 需要 6 天时间可以完成。

(1)AOV 网具有的性质⒈只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。

⒉只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。

⒊表示实际工程计划的AOE 网应该是无环的，并且存在唯一的入度过为0 的开始顶点和唯一的出度为0 的完成顶点。

(2)由事件v j 的最早发生时间和最晚发生时间的定义, 可以采取如下步骤求得关键活动:1. 从开始顶点v 1 出发, 令ve(1)=0, 按拓扑有序序列求其余各顶点的可能最早发生时间。

Ve(k)=max{ve(j)+dut(<j,k>)} （7.1 ）j ∈T其中T 是以顶点v k 为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。

如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n ，则说明网中有环，不能求出关键路径，算法结束。

2. 从完成顶点v n 出发，令vl(n)=ve(n) ，按逆拓朴有序求其余各顶点的允许的最晚发生时间: vl(j)=min{vl(k)-dut(<j,k>)}k ∈S其中S 是以顶点v j 是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。

关键路径法CPM（CriticalPathMethod关键路径法）是项目管理中最基本也是非常关键的一个概念，它上连着WBS（工作分解结构），下连着执行进度控制与监督。

关键路径是项目计划中最长的路线。

它决定了项目的总实耗时间。

项目经理必须把注意力集中于那些优先等级最高的任务，确保它们准时完成，关键路径上的任何活动的推迟将使整个项目推迟。

向关键路径要时间，向非关键路径要资源。

所以在进行项目操作的时候确定关键路径并进行有效的管理是至关重要的。

关键路径法关键路径法 - 定义关键路径法Critical Path Method，CPM)，又称关键线路法。

一种计划管理方法。

它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。

它用网络图表示各项工作之间的相互关系，找出控制工期的关键路线，在一定工期、成本、资源条件下获得最佳的计划安排，以达到缩短工期、提高工效、降低成本的目的。

CPM中工序时间是确定的，这种方法多用于建筑施工和大修工程的计划安排。

它适用于有很多作业而且必须按时完成的项目。

关键路线法是一个动态系统，它会随着项目的进展不断更新，该方法采用单一时间估计法，其中时间被视为一定的或确定的。

关键路径法关键路径法 - 起源关键路径法关键路线法是一种网络图方法，最早出现于20世纪50年代，由雷明顿-兰德公司(Remington- Rand)的JE克里(JE Kelly)和杜邦公司的MR沃尔克(MR Walker)在1957年提出的，用于对化工工厂的维护项目进行日程安排。

这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。

关键路径法关键路径法 - 原理与网络图设定步骤关键路径法关键路径法（CPM）是一种网络分析技术，是确定网络图当中每一条路线从起始到结束，找出工期最长的线路，也就是说整个项目工期的决定是由最长的线路来决定的。

数据结构课程设计Array报告院系：信息管理学院专业：软件工程目录一、问题的描述二、系统需求及分析1、简要介绍2、需求分析3、概要设计4、详细设计(1)数据结构(2)创建有向图的邻接表(3)计算各事件及活动的相关信息(4)输出有向图的相关信息(5)判断图中是否有回路(6)计算并输出关键活动(7)计算并输出关键路径(8)操作入口三、系统实现四、设计总结五、附件（完整源代码）一、问题的描述：关键路径问题（起评分：85）1、功能：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

2、数据：自行设计每个活动的前导活动和后续活动以及活动的进行时间，然后依据这些活动的前后次序，画出其网络图，选择存储结构。

3、操作：（1）求工程最短工期；（2）输出关键路径；（3）输出关键活动。

4、要求：界面友好，提示信息完整。

二、系统需求及分析：1、简要介绍：我们通常把计划、施工过程、生产流程、程序流程等都当成一个工程。

工程通常分为若干个称为“活动”的子工程。

完成了这些“活动”，这个工程就可以完成了。

我们通常用AOE-网来表示工程。

AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。

AOE-网可以用来估算工程的完成时间。

他可以使人们了解：(1). 研究某个工程至少需要多少时间?(2). 哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。

完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(Critical Path)。

关键路径可以很方便的让我们估算出某个工程最短的时间开销，以及这个工程中哪些活动，即哪些项目是主要的，是影响工程进度的关键，从而让我们对工程的实施做出更好的时间安排，并且可以分清主次，抓住核心工程，做到有的放矢。

关键路径（CriticalPath）引⼊拓扑排序主要是为解决⼀个⼯程能否顺序进⾏的问题，但有时还需要解决⼯程完成需要的最短时间问题。

这时仅仅是拓扑排序是不够的。

通过拓扑排序，可以有效地分析出⼀个有向图是否存在环；若不存在，那它的拓扑排序是什么？另⼀⽅⾯，利⽤求关键路径的算法，可以得到完成⼯程的最短⼯期及关键活动有哪些。

（摘⾃《⼤话数据结构》）定义事件：开始XX事情 | 完成XX事情活动：做XX事情源点：某流程的开始汇点：某流程的结束AOE⽹：在⼀个表⽰⼯程的带权有向图中，⽤顶点表⽰事件，⽤有向边表⽰活动，⽤边上的权值表⽰活动的持续时间，这种有向图的边表⽰活动的⽹，我们称之为AOE⽹（Activity On Edge Network）。

把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最⼤长度的路径叫关键路径，在关键路径上的活动叫关键活动。

（摘⾃《⼤话数据结构》）事件是⼀个点，活动是⼀条线。

举例以炒⼀盘⾁作为⽰例：将炒⼀盘⾁⽐作⼀个⼯程。

⼀位⼤⼈负责厨房的事情，⼀位⼩孩负责从院⼦⾥摘菜并送到厨房。

⼩孩从院⼦⾥摘菜并送到厨房需要1.5分钟。

⼤⼈准备⾁需要7分钟；准备菜需要1.5分钟；炒⾁需要2分钟；炒菜需要1分钟。

问题：这项⼯程的最短时间为多少？显然，该⼯程的流程不是这样：摘菜送到厨房（1.5分钟）->准备⾁（7分钟）->准备菜（1.5分钟）->炒⾁（2分钟）->炒菜（1分钟），共13分钟。

因为⼩孩摘菜的同时⼤⼈可以准备⾁；在炒⾁的后⾯阶段可以将菜放⼊锅⾥⼀起炒，这也符合⽇常实践。

⽽准备菜这个活动⼜受到“摘菜并送到厨房”和“准备⾁”这两个活动的制约：先有菜才能对菜进⾏处理！先处理好⾁才能处理菜吧，厨房⾥只有⼀个⼈。

⽤前⾯的“事件”、“活动”、“源点”和“汇点”来表⽰这个⼯程。

源点：开始准备⾁/开始摘菜送到厨房汇点：完成炒菜/完成炒⾁事件：开始摘菜并送到厨房>完成摘菜并送到厨房开始准备⾁>完成准备⾁开始准备菜>完成准备菜开始炒⾁>完成炒⾁开始炒菜>完成炒菜约束条件：“完成准备⾁”和“完成摘菜并送到厨房”才能“开始准备菜”。

AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。

AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。

AOE网的性质：⑴只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；⑵只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。

关键活动：关键路径上的活动称为关键活动。

关键活动：e[i]=l[i]的活动由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。

关键路径长度是整个工程所需的最短工期。

与关键活动有关的量：⑴事件的最早发生时间ve[k]ve[k]是指从始点开始到顶点vk的最大路径长度。

这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。

⑵事件的最迟发生时间vl[k]vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。

⑶活动的最早开始时间e[i]若活动ai是由弧<vk , vj>表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。

因此，有：e[i]=ve[k]⑷活动的最晚开始时间l[i]活动ai的最晚开始时间是指，在不推迟整个工期的前提下，ai必须开始的最晚时间。

若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。

因此，有：l[i]=vl[j]-len<vk, vj>示例：所以：代码实现：??......。

数据结构——⼿⼯求解关键路径这⾥先回顾⼀下⼏个概念：AOE⽹AOE⽹是活动在边上的⽹（Activity On Edge network，AOE）的英⽂简称。

AOE⽹是⽤有向图来表⽰的，在有向图中，边表⽰活动，边具有权值，边的权值代表了活动的持续时间。

顶点表⽰事件，事件是图中新活动开始或者旧活动结束的标识。

与AOV⽹相同的是，AOE⽹也是有向⽆环图，不同的是在AOV⽹中顶点表⽰活动，边⽆权值，边代表活动之间的先后关系。

对于⼀个表⽰⼯程的AOE⽹，只存在⼀个⼊度为0的顶点，成为源点，表⽰整个⼯程的开始；也只有⼀个出度为0的顶点，称为汇点，表⽰整个⼯程的结束。

关键路径在AOE⽹中，从源点到汇点的所有路径中，具有最⼤路径长度的路径成为关键路径。

关键路径所代表的时间就是完成整个⼯期的最短时间。

关键路径上的活动（边）称为关键活动。

事件最早发⽣时间ve(k)设ve(k)代表事件（顶点）k的最早发⽣时间，即从源点到顶点k的路径中的最长者，即ve(k)=max{ve(j)+<j,k>}，其中j为k的前驱事件，且j可能有多个。

初始时，将源点事件的最早发⽣时间ve(0)设置为0。

事件最晚发⽣时间vl(k)设vl(k)代表事件（顶点）k的最晚发⽣时间，即在不推迟整个⼯程完成的前提下，事件k最迟必须发⽣的时间，即vl(k)=min{vl(j)-<k,j>}，其中j 为k的后继事件，j可能有多个。

对于汇点时间来说，它的最早发⽣时间是整个⼯程的结束时间，因此他的最早发⽣时间也是最迟发⽣时间，即初始时将汇点事件的最晚发⽣时间vl(n)设置为ve(n)。

活动最早发⽣时间e(i)设e(ak)代表当前活动（边）ak的最早发⽣时间，由于事件代表⼀个新活动的开始或⼀个旧活动的结束，因此事件的最早发⽣时间就是有这个事件所发出的活动的最早时间。

即若存在边ak1：<i,j>，ak2：<k,j>，则e(ak1)=e(ak2)=ve(i)。

数据结构（五）图---关键路径⼀：定义（⼀）最短时间我们要对⼀个流程图获得最短时间，就要分析他们的拓扑关系，并且找到当中的最关键的流程，这个流程的时间就是最短时间（⼆）AOE⽹（Activity On Edge Network）在⼀个表⽰⼯程的带权有向图中，⽤到的表⽰时间，⽤有向边表⽰活动，⽤边上权值表⽰活动的持续时间，这种有向图的边表⽰活动的⽹，我们称之为AOE⽹我们将AOE⽹中没有⼊边的顶点称为源点或始点，没有出边的顶点称为终点或者汇点正常情况下，AOE⽹只有⼀个源点⼀个终点例如下图AOE⽹，v0为源点，表⽰整个⼯程的开始，v9为终点，表⽰这个⼯程的结束。

顶点v0,v1,....v9分别表⽰事件弧<v0,v1>,<v0,v2>,...,<v8,v9>都表⽰⼀个活动，⽤a0,a1,...,a12表⽰补充：相⽐于AOV⽹AOV中不在意边的权值，不局限⼀个源点和⼀个终点，关注的是是否构成环AOE关注边的权值，来求得最短时间等信息，源点和终点都只有⼀个（三）关键路径路径上各个活动所持续的事件之和称为路径长度，从源点到终点具有最⼤长度的路径叫关键路径，在关键路径上的活动叫关键活动例如我们开始组装时候，我们就要等到前⾯的所有装备⼯作全部完成（按照最长路径来算），才能开始我们的组装任务。

所以我们的关键路径需要是最⼤长度的路径⼆：AOE和AOV（活动和事件|顶点与弧）AOE⽹是表⽰⼯程流程的，所以它就具有明显的⼯程的特性。

只有在某顶点所表⽰的事件发⽣后，从该顶点出发的各活动才能开始。

只有在进⼊某顶点的各活动都已经结束，该顶点所代表的事件才能发⽣。

AOE与AOV对⽐虽然都是⽤来对⼯程建模，但是还是有很⼤不同。

主要体现在：AOV⽹是顶点表⽰活动的⽹，他只描述活动之间的制约更新，AOE⽹是⽤边表⽰活动的⽹，边上的权值表⽰活动持续的时间AOE⽹是要建⽴在活动之间制约关系没有⽭盾的基础之上，再来分析完成整个⼯程⾄少需要多少时间，或者为缩短完成⼯程所需时间，应该加快哪些活动等问题三：四个必要参数在AOE⽹中顶点v表⽰时间，边e表⽰活动（⼀）事件最早发⽣时间etv（earliest time of vertex）即顶点Vk的最早发⽣时间（⼆）事件最晚发⽣时间ltv（lastest time of vertex）即顶点Vk的最晚发⽣时间，也就是每个顶点对应的事件最晚需要开始的事件，超出此事件将会延误整个⼯期（三）活动的最早开⼯时间ete（earliest time of edge）即弧ak的最早发⽣时间（四）活动的最晚开⼯时间lte（lastest time if edge）即弧的最晚发⽣时间，也就是不推迟⼯期的最晚开⼯时间总结（重点）：我们可以由事件的最早发⽣时间和事件的最晚发⽣时间求出活动的最早和最晚开⼯时间。

数据结构中关键路径算法的实现与应用摘要介绍求关键路经的算法，对于给出的事件结点网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。

关键词关键路径最少时间1：引言通常把计划、施工过程、生产流程、程序流程的都当成一个工程。

除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。

完成了这些“活动”的子工程，这个工程就可以完成了。

通常我们用有向图表示一个工程。

在这种有向图中，用顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行。

如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE（active on edges）网络。

AOE网络在某些工程估算方面非常有用。

他可以使人们了解：（1）：研究某个工程至少需要多少时间？（2）：那些活动是影响工程进度的关键？在AOE网络中，有些活动可以并行的进行。

从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。

这些路径的长度也可能不同。

完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。

这条路径长度就叫做关键路径（criti cal path）。

2：设计步骤：1: 以某一工程为蓝本，采用图的结构表示实际的工程计划的时间。

2: 调查以分析和预测这个工程计划个阶段的时间。

3: 用调查的结果建立ＡＯE网（Activity On Edge Network），即边表示活动的网络，并用图的形式表示。

4: 用图来存储这些信息。

5: 用CreateGraphic();函数建立AOE图。

数据结构路径的定义数据结构路径是指在一个数据结构中，从一个节点到另一个节点的一条路径。

这个路径可以是有向或无向的，可以经过多个节点，也可以只包含两个节点。

在计算机科学中，数据结构路径是非常重要的概念之一，它在图论、网络分析、算法设计等领域都有广泛应用。

首先，我们需要了解什么是数据结构。

简单来说，数据结构就是指存储和组织数据的方式和方法。

常见的数据结构包括数组、链表、树、图等。

其中，树和图都是非常重要的数据结构。

在树中，每个节点都有一个父节点和若干个子节点。

从一个节点到另一个节点的路径就是从起始点沿着父子关系一直走到目标点的过程。

例如，在下图所示的二叉搜索树中，从1号节点到7号节点有两条路径：1-3-7和1-6-7。

```5/ \3 8/ \ / \1 4 7 9\6```在图中，则没有父子关系这样明显的概念。

每个节点都可以与其他任何一个节点相连，并且连接可能是单向或双向的。

从一个节点到另一个节点的路径就是沿着图中的边从起始点到目标点的过程。

例如，在下图所示的无向图中，从1号节点到7号节点有两条路径：1-2-4-7和1-3-5-6-7。

```1 --2 -- 3| | |4 --5 -- 6|7```数据结构路径在算法设计中也有重要应用。

例如，最短路径算法就是通过计算两个节点之间的最短路径来解决问题的。

在计算机网络中，路由算法也是基于数据结构路径来实现的。

总之，数据结构路径是指从一个节点到另一个节点的一条路径。

它在树、图等数据结构中都有广泛应用，并且在算法设计、网络分析等领域也非常重要。

了解数据结构路径的定义和应用可以帮助我们更好地理解和应用相关算法和技术。

关键路径法c语言详解关键路径法是一种用于项目管理的技术，用于确定项目中最长的路径，即关键路径，以便有效地进行资源分配和时间管理。

在本文中，我们将详细介绍关键路径法的原理和应用，并使用C语言进行示例演示。

一、原理介绍关键路径法是一种基于网络图的分析方法，它将项目分解成一系列活动，并通过活动之间的依赖关系构建网络图。

在这个网络图中，每个活动表示一个任务，箭头表示任务之间的依赖关系。

根据活动的持续时间和依赖关系，我们可以计算出每个活动的最早开始时间（EST）和最晚开始时间（LST），从而确定关键路径。

关键路径是指项目中最长的路径，即这条路径上的活动不能延迟，否则会导致整个项目延迟。

关键路径上的活动被称为关键活动。

通过确定关键路径，项目管理者可以有效地分配资源和控制进度，以确保项目按时完成。

二、关键路径法的步骤1. 确定项目的活动和依赖关系：将项目分解成一系列活动，并确定它们之间的依赖关系。

活动可以使用字母或数字进行标识，依赖关系可以用箭头表示。

2. 构建网络图：根据活动和依赖关系，构建项目的网络图。

网络图可以使用邻接矩阵或邻接表表示。

3. 计算活动的最早开始时间（EST）：从起始节点开始，根据依赖关系和活动持续时间，计算每个活动的最早开始时间。

最早开始时间可以通过递归或拓扑排序算法计算得出。

4. 计算活动的最晚开始时间（LST）：从终止节点开始，根据依赖关系和活动持续时间，计算每个活动的最晚开始时间。

最晚开始时间可以通过逆序递归或拓扑排序算法计算得出。

5. 计算活动的总时差（TF）：根据最早开始时间和最晚开始时间，计算每个活动的总时差。

总时差可以通过最晚开始时间减去最早开始时间得出。

6. 确定关键路径：找出总时差为0的活动，这些活动构成了关键路径。

关键路径上的活动不能延迟，否则会延误整个项目。

三、C语言示例演示以下是一个使用C语言实现关键路径法的简单示例：```c#include <stdio.h>void calculate_early_start(int activity[], int duration[], int dependency[], int n, int est[]) {for (int i = 0; i < n; i++) {if (dependency[i] == -1) {est[i] = 0;} else {if (est[dependency[i]] + duration[dependency[i]] > est[i]) {est[i] = est[dependency[i]] + duration[dependency[i]];}}}}void calculate_late_start(int activity[], int duration[], int dependency[], int n, int est[], int lst[]) {lst[n - 1] = est[n - 1];for (int i = n - 2; i >= 0; i--) {if (dependency[i] == -1) {lst[i] = lst[i + 1] - duration[i];} else {if (est[i] > lst[i + 1] - duration[i]) {lst[i] = est[i];} else {lst[i] = lst[i + 1] - duration[i];}}}}void find_critical_activities(int est[], int lst[], int n) {printf("Critical activities: ");for (int i = 0; i < n; i++) {if (est[i] == lst[i]) {printf("%d ", i + 1);}}printf("\n");}int main() {int n = 6; // Number of activitiesint activity[] = {1, 2, 3, 4, 5, 6}; // Activity IDsint duration[] = {5, 3, 2, 4, 2, 6}; // Durationsint dependency[] = {-1, 1, 2, 1, 4, 3}; // Dependency (indexstarts from 0)int est[n]; // Early start timesint lst[n]; // Late start timescalculate_early_start(activity, duration, dependency, n, est); calculate_late_start(activity, duration, dependency, n, est, lst);printf("Activity\tDuration\tEST\t\tLST\n");for (int i = 0; i < n; i++) {printf("%d\t\t%d\t\t%d\t\t%d\n", activity[i], duration[i], est[i], lst[i]);}find_critical_activities(est, lst, n);return 0;}```在上述示例中，我们使用了一个包含6个活动的项目进行演示。