强化阶段：图论算法应用 - 关键路径与AOE网深入解析

在蓝桥杯的备考过程中，图论算法是一个重要的考点，其中关键路径与AOE网（Activity On Edge Network，边表示活动的网）是图论应用中的经典问题。本文将深入解析事件最早/最晚发生时间的计算方法，并通过实例演示如何求解工程调度中的临界活动。

一、关键路径与AOE网基础

关键路径是指在一个工程或项目中，从开始到结束的一系列关键活动组成的路径，这些活动的总持续时间决定了整个项目的最短完成时间。AOE网是一种特殊的有向无环图（DAG），其中顶点表示事件，边表示活动，边上的权值表示活动的持续时间。

二、事件最早发生时间计算

在AOE网中，事件最早发生时间是指从源点到该事件的最长路径长度。计算步骤如下：

1. 初始化：将源点的最早发生时间设为0，其他事件的最早发生时间设为无穷大。

2. 迭代计算：从源点开始，按照拓扑排序的顺序，逐步计算每个事件的最早发生时间。对于每个事件，遍历其所有前驱事件，取其中最早发生时间加上对应活动持续时间的最大值作为该事件的最早发生时间。

三、事件最晚发生时间计算

事件最晚发生时间是指在不推迟整个工程完成时间的前提下，该事件允许的最晚发生时间。计算步骤如下：

1. 初始化：将汇点的最晚发生时间设为整个工程的最短完成时间，其他事件的最晚发生时间设为无穷大。

2. 迭代计算：从汇点开始，按照逆拓扑排序的顺序，逐步计算每个事件的最晚发生时间。对于每个事件，遍历其所有后继事件，取其中最晚发生时间减去对应活动持续时间的最小值作为该事件的最晚发生时间。

四、临界活动求解

临界活动是指在关键路径上的活动，这些活动的任何延迟都会导致整个工程完成时间的延迟。求解步骤如下：

1. 根据前面计算得到的事件最早发生时间和最晚发生时间，计算每个活动的最早开始时间和最晚开始时间。

2. 找出所有最早开始时间等于最晚开始时间的活动，这些活动即为临界活动。

五、实例演示

假设有一个工程包含以下活动：A(3天)、B(2天)、C(4天)、D(1天)、E(2天)，活动之间的依赖关系如下：A->B, A->C, B->D, C->D, D->E。通过AOE网建模并计算，可以得到关键路径为A->C->D->E，总持续时间为9天。进一步计算可以得到临界活动为A、C、D和E。

总之，掌握关键路径与AOE网的求解方法对于解决工程调度问题具有重要意义。通过本文的学习，相信大家能够更好地理解和应用这些图论算法知识，为蓝桥杯考试做好充分准备。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！