拓扑排序、关键路径分析

关键路径问题一、问题描述设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

二、基本要求1.对一个描述工程的AOE网，应判断其是否能够顺利进行。

2.若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点，最早发生时间和最迟发生时间。

三、题目分析1．由题目可知，要解决问题，首先要建立一个描述工程的AOE网络，即一个带权的有向无环图，可采用邻接表创建图。

2．利用拓扑排序的方法，判断出工程是否可以顺利，并求出各个顶点代表事件的最早发生时间。

汇点的最早发生时间即为完成整项工程所需的最短时间。

3．利用拓扑逆序，求出各个顶点代表事件的最晚发生事件。

4．由顶点的最早和最晚发生时间求出各个活动的最早最晚发生时间。

6．确定出哪些活动是关键活动。

四、逻辑结构有向无环图的逻辑结构可表示为：VR={<v，w>|v，w ∈V且P(v，w)，<v，w>表示从v到w的有向弧,谓词P(v，w)定义了弧<v，w>的意义或信息(在AOE网中即为完成活动所需的时间)}五、存储结构对于本问题中的有向无环图，采用邻接表作为存储结构。

邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i 个单链表中的结点表示依附于顶点v i的边。

每个结点由3个域组成，其中邻接点域指示与顶点v i邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息。

每个链表上附设一个表头结点。

例如：六、算法设计按照对题目的分析，本算法主要分为四个模块：1．采用邻接表存储结构创建图设计思路：输入图中顶点及弧的个数，然后依次输入各个顶点的名称。

建立存放顶点元素的数组G. vertices，将顶点名称存入其数据G.vertices[i].data，其指针域G.vertices[i].firstarc 初始化为空。

输入各条弧及其权值，对每个顶点采用逆序插入结点的方式建立单链表。

关键路径理解和实现（Java）一、什么是关键路径在项目管理中，关键路径指的是完成一个项目所需的最长时间，也就是说在没有任何延误的情况下，项目完成的最短时间。

关键路径法是一种用于确定项目完成时间的方法，它能够帮助项目管理者合理安排项目的工作，提高项目的执行效率。

在项目中，每一个任务都有其开始时间和完成时间，而不同的任务之间可能存在依赖关系，即某些任务的开始时间取决于其他任务的完成时间。

通过确定各个任务之间的依赖关系，可以建立项目的网络图，通过这个图可以找出最长的路径，即关键路径。

二、关键路径的重要性1. 有效管理时间关键路径法能够帮助项目管理者了解到项目所需的最长时间，可以在这个基础上对项目的进度进行合理安排，避免出现拖延等问题，从而保证项目能够按时完成。

2. 资源分配通过确定关键路径，项目管理者可以清楚地了解到哪些任务是关键的、哪些是可以并行进行的，可以有效地分配资源，提高资源利用率。

3. 风险控制关键路径法可以帮助项目管理者及时发现项目进度偏差，及时调整方案，降低项目风险。

三、关键路径的实现（Java）在实际项目管理中，我们通常会借助计算机软件来帮助我们确定项目的关键路径。

下面将介绍如何使用Java语言来实现关键路径的计算。

1. 定义任务节点和任务之间的依赖关系我们需要定义任务节点和任务之间的依赖关系。

我们可以使用图的数据结构来表示这些任务节点和它们之间的依赖关系。

我们可以定义一个Task类来表示任务节点，这个类包括任务的开始时间、完成时间等属性。

另外，我们还可以定义一个Graph类来表示整个项目的网络图，这个类包括任务节点之间的依赖关系等属性。

2. 计算最早开始时间和最晚开始时间在确定了任务节点和它们之间的依赖关系之后，我们可以利用拓扑排序算法来计算每个任务节点的最早开始时间和最晚开始时间。

计算最早开始时间时，我们可以从项目的起点开始，按照拓扑排序的顺序计算每个任务节点的最早开始时间，这个时间表示的是在没有任何延误的情况下，该任务节点可以开始的最早时间。

2023洛谷模拟试题解析引言概述：2023年洛谷模拟试题是一项重要的考试，对于参加考试的学生来说，了解试题的解析是提高考试成绩的关键。

本文将对2023洛谷模拟试题进行详细解析，帮助考生更好地理解试题内容，提高解题能力。

正文内容：1. 第一大点：试题类型1.1 选择题：解析选项的含义，注意干扰项的排除。

1.2 填空题：分析题目要求，确定填空内容的格式和范围。

1.3 编程题：理解题目要求，设计合理的算法，注意边界条件和优化策略。

2. 第二大点：数据结构与算法2.1 数组与链表：比较两者的特点和适用场景，分析题目中对数据结构的要求。

2.2 栈与队列：解释栈和队列的概念，讨论它们在算法中的应用。

2.3 树与图：介绍树和图的基本概念，分析与它们相关的算法问题。

3. 第三大点：动态规划3.1 动态规划的基本思想和应用场景。

3.2 分析动态规划问题的状态转移方程，推导出解题的递推公式。

3.3 讨论动态规划中的优化策略，如剪枝和记忆化搜索。

4. 第四大点：图论算法4.1 最短路径算法：介绍Dijkstra算法和Floyd-Warshall算法的原理与应用。

4.2 最小生成树算法：解析Prim算法和Kruskal算法的实现过程和时间复杂度。

4.3 拓扑排序和关键路径：讲解拓扑排序的概念和算法，分析关键路径的求解方法。

5. 第五大点：数论与组合数学5.1 质数与素数：介绍质数和素数的定义，讨论相关的算法和性质。

5.2 欧几里得算法：解析最大公约数和最小公倍数的计算方法。

5.3 排列组合：讲解排列和组合的概念，分析相关问题的解题思路。

总结：综上所述，2023年洛谷模拟试题的解析主要包括试题类型、数据结构与算法、动态规划、图论算法以及数论与组合数学。

了解试题类型和解题思路对于考生提高解题能力至关重要。

同时，熟悉各种数据结构和算法的特点和应用场景，以及动态规划、图论算法和数论与组合数学的基本概念和解题方法，也是取得好成绩的关键。

数据结构的应用的拓扑排序与关键路径算法拓扑排序与关键路径算法是数据结构中重要的应用之一。

拓扑排序通过对有向图的节点进行排序，使得对于任意一条有向边(u,v)，节点 u 在排序中都出现在节点 v 之前。

关键路径算法则是用来确定一个项目的关键活动和最短完成时间。

拓扑排序的实现可以通过深度优先搜索或者广度优先搜索来完成。

深度优先搜索是递归地访问节点的所有未访问过的邻居节点，直到没有未访问过的邻居节点为止，然后将该节点添加到拓扑排序的结果中。

广度优先搜索则是通过使用队列来实现的，将节点的邻居节点逐个入队并进行访问，直到队列为空为止。

无论使用哪种方法，拓扑排序都可以通过判断节点的入度来进行。

拓扑排序在很多实际问题中都有广泛应用。

比如在任务调度中，拓扑排序可以用来确定任务间的依赖关系和执行顺序；在编译原理中，拓扑排序可以用来确定程序中变量的定义和使用顺序。

关键路径算法用于确定项目中的关键活动和最短完成时间。

它通过计算每个活动的最早开始时间和最晚开始时间，以及每个活动的最早完成时间和最晚完成时间来实现。

具体步骤如下：1. 构建有向加权图，其中节点表示项目的活动，有向边表示活动间的先后关系，边的权重表示活动的持续时间。

2. 进行拓扑排序，确定活动的执行顺序。

3. 计算每个活动的最早开始时间，即从起始节点到该节点的最长路径。

4. 计算每个活动的最晚开始时间，即从终止节点到该节点的最长路径。

5. 根据每个活动的最早开始时间和最晚开始时间，可以确定关键活动，即最早开始时间与最晚开始时间相等的活动。

6. 计算整个项目的最短完成时间，即从起始节点到终止节点的最长路径。

拓扑排序与关键路径算法在工程管理、任务调度、生产流程优化等领域都有重要应用。

它们能够帮助我们有效地组织和管理复杂的项目，提高工作效率和资源利用率。

在实际应用中，我们可以借助计算机编程以及各种图算法库来实现这些算法，从而更快速、准确地解决实际问题。

综上所述，拓扑排序与关键路径算法是数据结构的重要应用之一。

关键路径法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个活动的项目进行演示。

拓扑排序算法
算法实现： a) 数据结构：indgr[i]: 顶点i的入度; stack[ ]: 栈 b) 初始化:top=0 (栈顶指针置零) c) 将初始状态所有入度为0的顶点压栈 d) I=0 (计数器) e) while 栈非空(top>0) i. 栈顶的顶点v出栈；top-1; 输出v；i++； ii. for v的每一个后继顶点u 1. indgr[u]--; u的入度减1 2. if （u的入度变为0） 顶点u入栈 f) 算法结束 这个程序采用栈来找出入度为0的点，栈里的顶点，都是入度为0的点。 我们结合上图详细讲解： B D C A 栈：A 开始时，只有A入 度为0，A入栈。
1
4 8 5 6 9
引入
在AOV网中，有向边代表子工程（活动）的先后关系，我们把一条有向边起点 的活动成为终点活动的前驱活动，同理终点的活动称为起点活动的后继活动。而只 有当一个活动全部的前驱全部都完成之后，这个活动才能进行。例如在上图中，只 有当工程1完成之后，工程2、3、4、5、6才能开始进行。只有当2、3、4全部完成 之后，7才能开始进行。 一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关 系的自相矛盾。 1 2
关键路径
AOE网络要研究的问题是完成整个工程至少需要多少时间？哪些活动是影响工程 进度的关键？ 下面先讨论一个事件的最早发生时间和一个活动的最早开始时间。如下图，事件Vj 必须在它的所有入边活动eik（1≤k≤n）都完成后才能发生。活动eik（1≤k≤n） 的最早开始时间是与它对应的起点事件Vik的最早发生时间。所有以事件Vj为起点事 件的出边活动ejk（1≤k≤m）的最早开始时间都等于事件Vj的最早发生时间。所以， 我们可以从源点出发按照上述方法，求出所有事件的最早发生时间。

代谢组学中的拓扑分析方法拓扑分析方法在代谢组学中可以用于研究代谢网络的结构和功能，并揭示代谢网络中的关键模块和关键代谢物。

以下是一些常见的拓扑分析方法：1. 网络分析：通过构建代谢网络模型，可以使用网络分析方法来研究代谢网络的拓扑结构、节点的重要性以及模块化结构等。

例如，可以使用节点度中心性分析来评估代谢物的重要性，使用聚类分析来识别代谢网络中的功能模块等。

2. 中心性分析：中心性分析是一种常见的拓扑分析方法，用于评估网络中节点的重要性。

在代谢网络中，可以使用节点度中心性、介数中心性和接近度中心性等指标来评估代谢物的重要性。

较高的中心性指标表明节点在代谢网络中具有更重要的作用。

3. 模块性分析：模块性分析是一种拓扑分析方法，用于识别代谢网络中的功能模块。

功能模块是指在代谢网络中具有紧密相连的一组代谢物。

可以使用聚类分析、模块性优化算法等方法来鉴定和分析功能模块中的代谢关系，从而帮助理解代谢网络的功能和调控机制。

4. 关键路径分析：关键路径分析是一种拓扑分析方法，用于识别代谢网络中的关键代谢物和关键途径。

关键路径是指在代谢网络中连接起点和终点的最短路径，通过分析关键路径上的代谢物和途径，可以识别具有重要生物学功能的代谢反应和调控机制。

5. 高级拓扑分析方法：除了以上基本的拓扑分析方法外，还有一些高级的拓扑分析方法可以应用于代谢组学中，如基于网络的马尔科夫链蒙特卡洛方法、基于典型相关分析的路径勘探等。

这些方法可以用于潜在途径和代谢子的预测、生物标志物的筛选等。

总之，拓扑分析方法在代谢组学中可以用于探索代谢网络的结构和功能，揭示代谢物的重要性和调控机制，从而为代谢疾病的研究和治疗提供理论基础。

2．有向图在实际问题中的应用 一个有向图可以表示一个施工流程图，或产品生产流程
图，或数据流图等。设图中每一条有向边表示两个子工程之 间的先后次序关系。
若以有向图中的顶点来表示活动，以有向边来表示活动 之间的先后次序关系，则这样的有向图称为顶点表示活动的 网 (Activity On Vertex Network)，简称AOV网。
这样，每个活动允许的时间余量就是l(i) - e(i)。而关键活动 就是l(i) - e(i) = 0的那些活动，即可能的最早开始时间e(i)等于 允许的最晚开始时间l(i)的那些活动就是关键活动。
4．寻找关键活动的算法 求AOE网中关键活动的算法步骤为： （1）建立包含n+1个顶点、e条有向边的AOE网。其中，顶
（4）从汇点vn开始，令汇点vn的最晚发生时间vl[n]=ve[n]， 按逆拓扑序列求其余各顶点k(k=n-1,n-2,…,2,1,0)的最晚发生 时间vl[k]；
（5）计算每个活动的最早开始时间e[k] (k=1,2,3,…,e)； （6）计算每个活动的最晚开始时间l[k] (k=1,2,3,…,e)； （7）找出所有e[k]= l[k]的活动k，这些活动即为AOE网的 关键活动。
上述算法仅能得到有向图的一个拓扑序列。改进上述 算法，可以得到有向图的所有拓扑序列。
如果一个有向图存在一个拓扑序列，通常表示该有向 图对应的某个施工流程图的一种施工方案切实可行；而 如果一个有向图不存在一个拓扑序列，则说明该有向图 对应的某个施工流程图存在设计问题，不存在切实可行 的任何一种施工方案。
事件可能的最早开始时间υe(k)：对于顶点υk代表的事件， υe(k)是从源点到该顶点的最大路径长度。在一个有n+1个事 件的AOE网中, 源点υ0的最早开始时间υe(0)等于0。事件υk （k=1,2,3,…,n）可能的最早开始时间υe(k)可用递推公式表 示为：

9.1静态查找表 静态查找表
6 a 5 d 4
b
1 1 e
8 7
g 4 h
2 k
c 2 4 f
a b c d e f g h k ve vl
0 0 0 0 0 0 15 14 18 6 4 5 5 7 0 11 0 7 0 18 18 18 18 18 18 18 18 18 0 6 6 8 8 10 16 14 7
事件发生时间的计算公式： 事件发生时间的计算公式： ve(源点 = 0； 源点) 源点 ； ve(j) = Max{ve(i) + dut(<i, j>)} <i,j>表示以 为弧头的弧 表示以j为弧头的弧 表示以 vl(汇点 = ve(汇点 ； 汇点) 汇点)； 汇点 汇点 vl(i) = Min{vl(j) – dut(<i, k>)} <i,j>表示以 为弧尾的弧 表示以i为弧尾的弧 表示以
（２）弗洛伊德算法的基本思想是：
的所有可能存在的路径中， 从 vi 到 vj 的所有可能存在的路径中，选出一条长 度最短的路径。
可以用如下递推公式描述： 可以用如下递推公式描述： D-1[i][j]=cost[i][j] Dk [i][j]=min{Dk-1[i][j],Dk-1[i][k]+Dk-1[k][j]}(0≤k≤n-1) 其中， 中存放着序号为i的结点到序号为 其中，cost[i][j]中存放着序号为 的结点到序号为 的结点之 中存放着序号为 的结点到序号为j的结点之 表示从结点vi到结点 到结点vj的路径 间的权值 ； Dk[i][j](0≤k≤n-1) 表示从结点 到结点 的路径 上所经过的结点序号不大于k的最短路径长度 的最短路径长度。 上所经过的结点序号不大于 的最短路径长度。

路网拓扑结构分析及路径规划优化随着交通工具的不断升级，道路网络拓扑结构的优化与路径规划问题变得日益重要。

结构合理的路网能够实现更快速、更高效的交通，而路径规划则直接影响到驾驶行为的安全和交通效率。

本文将就路网拓扑结构分析及路径规划优化进行探讨。

一、路网拓扑结构的分析路网拓扑结构分析指的是对道路网络进行节点和边的抽象，建立数学模型，以揭示其内在的结构和规律。

常见的路网拓扑结构分析方法有最短路径算法、最小生成树算法、网络流算法等。

最短路径算法是利用图论中的最短路径问题，寻找两个节点之间的最短路径。

该算法包括迪杰斯特拉算法和弗洛伊德算法两种方法。

迪杰斯特拉算法适用于稠密图，优先考虑离出发点近的节点；而弗洛伊德算法适用于稀疏图，通过动态规划找到任意两个节点之间的最短路径。

最小生成树算法则是用于求带权无向图的生成树的算法，常见的有普里姆算法和克鲁斯卡尔算法。

普里姆算法是从任意起点开始，每次选择一条连通的最小边长的边并加入生成树中，直到生成树中的边数等于总点数减一为止。

而克鲁斯卡尔算法则是将所有边按权值从小到大排序，每次选取一条边加入生成树中，直到生成树中的边数等于总点数减一为止。

网络流算法则是用于解决最大流和最小割问题的算法，本质上也是一种路径规划。

该算法包括最大流算法和最小费用最大流算法等。

最大流算法是指在图中确定一个源点和汇点，不断地调整流量，使得从源点到汇点的流量最大。

而最小费用最大流算法则是在满足最大流的情况下，使得经过的边的权值之和最小。

二、路径规划的优化路径规划是指在复杂的路网中选择经过路径的过程。

该过程中既要考虑路线的最短时间，也要考虑道路的拥堵情况、路径的流畅性、交通安全等因素。

路径规划优化的目标就是在满足条件的同时，尽可能提高路径的效率。

目前常见的路径规划方法包括Dijkstra算法、A*算法、RS算法等。

Dijkstra算法是基于最短路径算法的一种路径规划方法，用于找到从起点到其他所有网络节点的最短路径。

拓扑序列：有向图D的一个顶点序列称作一个拓扑序列，如果该 序列中任两顶点v 、u ，若在D中v是u前趋，则在序列中v也是u 前趋。
对有向图进行如下操作：按照有向图给出的次序关系，将图 中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶 点，则可以人为加上任意的次序关系。由此所得顶点的线性序列 称之为拓扑有序序列。
v3 v5
v9
v8
v4
v6
13 2020/8/4
7.5.2 关键路径（4）
在AOE网络中， 有些活动顺序进行，有些活动并行进行。
从源点到各个顶点，以至从源点到汇点的有向路径可能不止 一条。这些路径的长度也可能不同。完成不同路径的活动所 需的时间虽然不同，但只有各条路径上所有活动都完成了， 整个工程才算完成。
例：
C0
C1
C2
C0
C1
C2
C3
C4
C5
(a) 有向无环图
C0
C1
C2
C3
C4
C5
(b) 输出C4
C1
C2
C3
C5
(c) 输出顶点C0
9 2020/8/4
C3
C5
(d) 输出顶点C3
7.5.1拓扑排序(Topological Sort)（7）
C1
C2
C1
C5 (e) 输出顶点C2
C5 (f) 输出顶点C1
因此，完成整个工程所需的时间取决于从源点到汇点的最长 路径长度，即在这条路径上所有活动的持续时间之和。这条 路径长度最长的路径就叫做关键路径(Critical Path)。
子工程所需时间。 问：哪些子工程是“关键工程”？ 即：哪些子工程将影响整个工程的完成期限的。
首先了解一些基本概念：

Dijkstra算法
如何找到Vk?
min( D[i] + dur(i,k)) i = 0,1,…k-1
Vk
S
Dijkstra算法
V5
V0
10
30 10
V4
20
V1 V2
V3
S={V0} D[0]=0
S={V0,} D[3] = 50 S={V0,V2,V4,V3,V5}
Dijkstra算法实现
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortestPathTable &D){ for(v=0;v<G.vexnum;++v){ final[v]=FALSE; //S中的顶点 D[v]=G.arcs[v0][v];//v0到v的路径的长度 for(w=0;w<G.vexnum;++w) p[v][w]=FALSE; if(D[v]<INFINITY){//V0的邻接点 p[v][v0]=TRUE; p[v][v]=TRUE; }//if }//for final[v0]=TRUE;
Floyd 算法
首先对顶点进行编号，n个顶点对应1……n个整 数，分别叫做V1，V2,……，Vn 显然，顶点vi和vj之间的最短路径通过了n个 顶点的某些顶点。
Floyd 算法
•偏序就是集合中的部分成员可以比较。 •全序是集合中的任何成员之间都可以比较。 B A C 偏序 D A C 全序 B D
拓扑排序
按照有向图给出的次序关系，将图中顶点排成 一个线性序列，对于有向图中没有限定次序关系 的顶点，则可以人为加上任意的次序关系。
由此所得顶点的线性序列称之为拓扑有序序 列

基本概念：
AOE网：带权的有向图，其中，顶点表示事件，弧表示活 动，权表示活动持续的时间。
关键路径：AOE-网中有些活动可以并行的进行，所以完 成工程的最短时间是从开始点到完成点的最长路径的 长度（这里所说的长度是指路径上各个活动持续时间 之和，不是路径上弧的数目）。路径长度最长的路径 叫做关键路径。
a5=1 7
v9 a8=7
v8 a11=4
a3=5
4
v4 a6=2
5
a9=4 11
v6
7
从ve（0）=0开始向后推.
Ve（j）=Max{ve（i）+dut（〈i,j〉）}
(j=1，2….n-1)
1 求活动最迟发生时间 6
a1=6 v2 a4=1
16v7
a7=9
a10=2 18
v9
0 v1 a2=4
a6=12
4 a5=7 6
el a1 0 0 a2 5 5 a3 0 7 a4 0 7 a5 9 16 a6 23 23 a7 15 15 a8 15 15 a9 5 5 a10 27 27 a11 27 27 a12 35 35 a13 41 41
v5 a8=7
v3 a5=1 7
v8 a11=4
a3=5
6
v4
8 a6=2
a9=4 14
v6
10
从vl(9）=18开始向回推（倒计时）。 Ve（i）=Min{vl（j）- dut（〈i,j〉）}
(j=n-2,n-3,----,0)
例： 对下面的AOE网络，试回答下列问题： ve vl
(1)列出所有的关键路径; (2)完成整个工程至少需要多少时间?
最早发生时间：假设开始点是V1，从V1到Vi的最长的路径 的长度叫做事件Vi的最早发生时间。

《大话数据结构》笔记——第7章图（三）文章目录7.8 拓扑排序7.8.1 拓扑排序介绍7.8.2 拓扑排序算法7.9 关键路径7.9.1 关键路径算法原理7.9.2 关键路径算法7.10 回顾总结7.8 拓扑排序说了两个有环的图应用，现在我们来谈谈无环的图应用。

无环，即是图中没有回路的意思。

7.8.1 拓扑排序介绍在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为 AOV 网（ Activity On Vertex Network ）。

AOV 网中的弧表示活动之间存在的某种制约关系。

比如演职人员确定了，场地也联系好了，才可以开始进场拍摄。

另外就是 AOV 网中不能存在回路。

刚才已经举了例子，让某个活动的开始要以自己完成作为先决条件，显然是不可以的。

设 G=(V,E) 是一个具有 n 个顶点的有向图，V 中的顶点序列v1,v2, … ,vn ，满足若从顶点 vi 到 vj 有一条路径，则在顶点序列中顶点 vi 必在顶点 vj 之前。

则我们称这样的顶点序列为一个拓扑序列。

上图这样的 AOV 网的拓扑序列不止一条。

序列 v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 是一条拓扑序列，v0 v1v4 v3 v2 v7 v6 v5 v8 v10 v9 v12 v11 v14 v13 v15 v16 也是一条拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的 AOV 网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是 AOV 网。

一个不存在回路的 AOV 网，我们可以将它应用在各种各样的工程或项目的流程图中，满足各种应用场景的需要，所以实现拓扑排序的算法就很有价值了。

7.8.2 拓扑排序算法对 AOV 网进行拓扑排序的基本思路是：从 AOV 网中选择一个入度为 0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止。

拓扑排序算法
【例4-13】奖金 【问题描述】 由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理 Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准 来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出 了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案， 满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。 【输入格式】 第一行两个整数n,m，表示员工总数和代表数；以下m行，每行2个整数a,b，表 示某个代表认为第a号员工奖金应该比第b号员工高。 【输出格式】 若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。 【输入样例】 2 1 1 2 【输出样例】 201
4
3
上图就是一个出现环产生自相矛盾的情况。4是1的前驱，想完成1，必 须先完成4。3是4的前驱，而2是3的前驱，1又是2的前驱。最后造成想完成 1，必须先完成1本身，这显然出现了矛盾。
拓扑排序算法
拓扑排序算法，只适用于AOV网（有向无环图）。 把AOV网中的所有活动排成一个序列， 使得每个活动的所有前驱活动都排在该 活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。 一个AOV网的拓扑序列是不唯一的，例如下面的这张图，它的拓扑序列可以是： ABCDE，也可以是ACBDE，或是ADBCE。在下图所示的AOV网中，工程B和工程 C显然可以同时进行，先后无所谓；但工程E却要等工程B、C、D都完成以后才能进 行。 B C A D 构造拓扑序列可以帮助我们合理安排一个工程的进度，由AOV网构造拓扑序 列具有很高的实际应用价值。 算法思想： 构造拓扑序列的拓扑排序算法思想很简单： 选择一个入度为0的顶点并输出 然后从AOV网中删除此顶点及以此顶点为起点的所有关联边； 重复上述两步，直到不存在入度为0的顶点为止。 若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出 的顶点序列就是一种拓扑序列 从第四步可以看出，拓扑排序可以用来判断一个有向图是否有环。只有有 向无环图才存在拓扑序列。 E

indegree 0
5
4 3 2 1 1 5
0
1 2 3 4 5
0
0 0
0
1 0
3∧
栈S 0
p
5∧ 1 5∧
i=1 1, C1 count=5
k=5
0
5 C5 ∧
p=NULL
while(! StackEmpty(S)){ Pop(S, i); printf(i, G. vertices[i].data); ++count; for (p=G.vertices[i].firstarc; p; p=p->nextarc) { k = p->adjvex; if ( !(- -indegree[k]) ) Push(S, k); }//for }//while data firstarc 0 C0 1 1 C1 5 ∧ 2 C2 1 3 C3 ∧ 4 C4 5 C5 ∧
有向无环图
有向图（有环）
一、AOV-网(Activity On Vertices)
表示工程的有向图中，用顶点表示活动，用有向边<Vi, Vj>表示活动Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络。 （用顶点表示活动，弧表示活动间的优先关系的有向图）
在AOV网络中不能出现有向回路（即有向环）。

拓扑排序过程中涉及的数据和操作： 数据：有向图、顶点的入度； 操作： （1） 选择一入度为0顶点v，输出； （2） 将v邻接到的顶点 u 的入度减1。

为算法的有关数据选择设计存储结构(图用邻接表表示)
C0
C1
C2
C3
C4
C5
data firstarc C0 1 C1 5 0 C2 1 C3 C4 C5 0 0 0

详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。

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

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

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

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

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

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

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

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

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

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

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

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