📌 目录
📊数据结构：图—AOE-网全面解析
一、引言：AOE-网初印象 🔍
💡 AOE-网（Activity On Edge Network） 是一种用边表示活动、顶点表示事件的有向无环图（DAG）。边的权值代表活动耗时，顶点表示活动的开始或结束事件。它的核心价值在于帮助分析工程的最短工期和关键路径（决定工程进度的关键活动链）。
二、AOE-网基础：核心概念 🏗️
（一）三大元素解析 🧩
- 活动：有向边，带权值（如“编写代码(3天)”）。
- 事件：顶点，标志活动的起点/终点（如“代码编写完成”）。
- 源点/汇点：入度为0的起点（工程启动）、出度为0的终点（工程结束）。
（二）核心规则 ⚠️
必须是无环图！否则会出现活动循环依赖（如A等B完成、B等A完成），导致工期无法计算。
三、AOE-网关键计算：四步分析法 ⏳
（一）步骤1：拓扑排序 🔢
📌 对DAG进行拓扑排序，确定事件的先后顺序（如“需求分析”必须在“编码”前完成）。
（二）步骤2：计算事件时间参数
1. 最早发生时间（ v e ve ve） 🌅
- 定义：从源点到该事件的最长路径耗时（并行活动取最长路径，避免延误后续）。
- 计算：
- 源点 v e ( 源点 ) = 0 ve(源点) = 0 ve(源点)=0
- 其他事件 v e ( j ) = max { v e ( i ) + 活动 i → j 耗时 } ve(j) = \max\{ve(i) + 活动i→j耗时\} ve(j)=max{ve(i)+活动i→j耗时}
2. 最迟发生时间（ v l vl vl） 🌙
- 定义：不延误工程的前提下，事件最晚发生时间（从汇点倒推）。
- 计算：
- 汇点 v l ( 汇点 ) = v e ( 汇点 ) vl(汇点) = ve(汇点) vl(汇点)=ve(汇点)（工程总工期）
- 其他事件 v l ( i ) = min { v l ( j ) − 活动 i → j 耗时 } vl(i) = \min\{vl(j) - 活动i→j耗时\} vl(i)=min{vl(j)−活动i→j耗时}
（三）步骤3：计算活动时间参数
1. 最早开始时间（ e e e） 🌱
- 公式： e ( 活动 i → j ) = v e ( i ) e(活动i→j) = ve(i) e(活动i→j)=ve(i)（事件i最早发生时，活动可开始）。
2. 最迟开始时间（ l l l） 🌿
- 公式： l ( 活动 i → j ) = v l ( j ) − 活动耗时 l(活动i→j) = vl(j) - 活动耗时 l(活动i→j)=vl(j)−活动耗时（不延误工程的最晚开始时间）。
3. 关键活动判定 ⚡
当 e = l e = l e=l 时，该活动为关键活动（无时间余量，延误必拖慢总工期）。
（四）步骤4：确定关键路径 🗺️
关键活动连成的路径即为关键路径，其总耗时为工程最短工期。例如：
- 活动链
A→B→D耗时7天，A→C→D耗时7天，均为关键路径。
四、AOE-网实战：工程管理应用 🚀
（一）核心价值场景 🎯
- 工期优化：优先压缩关键活动耗时（如给“编码”活动增加人力）。
- 资源调度：非关键活动可灵活安排（如“调研”活动有1天缓冲期，可延后启动）。
（二）案例：软件开发流程 💻
- 活动链：
需求评审(0天)→设计(5天)→编码(7天)→测试(0天)（关键路径，总工期12天）
需求评审→调研(3天)→原型优化(2天)→测试（非关键路径，总工期5天，有7天缓冲）
五、AOE-网例题🙏
（一）题目描述👦
如图下图所示的AOE-网:
(1)求这个工程最早可能在什么时间结束;
(2)求每个活动的最早开始时间和最 迟开始时间;
(3)确定哪些活动是关键活动｡
（二）题目解析👧
1、明确AOE-网结构💪
顶点：1、2、3、4、5、6
边（活动）及权值：
- 1 → 2 1 \to 2 1→2，权值 2 2 2
- 1 → 3 1 \to 3 1→3，权值 15 15 15
- 3 → 2 3 \to 2 3→2，权值 4 4 4
- 2 → 4 2 \to 4 2→4，权值 10 10 10
- 2 → 5 2 \to 5 2→5，权值 19 19 19
- 3 → 5 3 \to 5 3→5，权值 11 11 11
- 4 → 6 4 \to 6 4→6，权值 6 6 6
- 5 → 6 5 \to 6 5→6，权值 5 5 5
2、表格1：事件（顶点）时间参数计算👍
| 事件（顶点） | 最早发生时间 v e ve ve | 最迟发生时间 v l vl vl | 计算逻辑（ v e ve ve按拓扑序， v l vl vl按逆拓扑序） |
|---|---|---|---|
| 1 | 0 0 0 | 0 0 0 | 源点，无前置事件， v e = 0 ve=0 ve=0；逆拓扑序中为起始点， v l = 0 vl=0 vl=0 |
| 2 | max { 0 + 2 , 15 + 4 } = 19 \max\{0+2,15+4\}=19 max{0+2,15+4}=19 | min { 37 − 10 , 38 − 19 } = 19 \min\{37-10,38-19\}=19 min{37−10,38−19}=19 | v e ve ve取 1 → 2 1 \to 2 1→2和 1 → 3 → 2 1 \to 3 \to 2 1→3→2的最大值； v l vl vl取 2 → 4 2 \to 4 2→4和 2 → 5 2 \to 5 2→5的最小值 |
| 3 | 0 + 15 = 15 0+15=15 0+15=15 | min { 19 − 4 , 38 − 11 } = 15 \min\{19-4,38-11\}=15 min{19−4,38−11}=15 | v e ve ve仅 1 → 3 1 \to 3 1→3； v l vl vl取 3 → 2 3 \to 2 3→2和 3 → 5 3 \to 5 3→5的最小值 |
| 4 | 19 + 10 = 29 19+10=29 19+10=29 | 43 − 6 = 37 43-6=37 43−6=37 | v e ve ve仅 2 → 4 2 \to 4 2→4； v l vl vl由 4 → 6 4 \to 6 4→6推导 |
| 5 | max { 19 + 19 , 15 + 11 } = 38 \max\{19+19,15+11\}=38 max{19+19,15+11}=38 | 43 − 5 = 38 43-5=38 43−5=38 | v e ve ve取 2 → 5 2 \to 5 2→5和 3 → 5 3 \to 5 3→5的最大值； v l vl vl由 5 → 6 5 \to 6 5→6推导 |
| 6 | max { 29 + 6 , 38 + 5 } = 43 \max\{29+6,38+5\}=43 max{29+6,38+5}=43 | 43 43 43 | 汇点， v e ve ve取所有入边最大值， v l = v e vl=ve vl=ve |
3、表格2：活动（边）时间参数计算👊
| 活动（边） | 起点 | 终点 | 边权 w w w | 最早开始 e = v e ( 起点 ) e=ve(起点) e=ve(起点) | 最迟开始 l = v l ( 终点 ) − w l=vl(终点)-w l=vl(终点)−w | 时间余量 l − e l-e l−e | 关键活动（ l − e = 0 l-e=0 l−e=0） |
|---|---|---|---|---|---|---|---|
| 1 → 2 1 \to 2 1→2 | 1 | 2 | 2 2 2 | 0 0 0 | 19 − 2 = 17 19-2=17 19−2=17 | 17 17 17 | 否 |
| 1 → 3 1 \to 3 1→3 | 1 | 3 | 15 15 15 | 0 0 0 | 15 − 15 = 0 15-15=0 15−15=0 | 0 0 0 | 是 |
| 3 → 2 3 \to 2 3→2 | 3 | 2 | 4 4 4 | 15 15 15 | 19 − 4 = 15 19-4=15 19−4=15 | 0 0 0 | 是 |
| 2 → 4 2 \to 4 2→4 | 2 | 4 | 10 10 10 | 19 19 19 | 37 − 10 = 27 37-10=27 37−10=27 | 8 8 8 | 否 |
| 2 → 5 2 \to 5 2→5 | 2 | 5 | 19 19 19 | 19 19 19 | 38 − 19 = 19 38-19=19 38−19=19 | 0 0 0 | 是 |
| 3 → 5 3 \to 5 3→5 | 3 | 5 | 11 11 11 | 15 15 15 | 38 − 11 = 27 38-11=27 38−11=27 | 12 12 12 | 否 |
| 4 → 6 4 \to 6 4→6 | 4 | 6 | 6 6 6 | 29 29 29 | 43 − 6 = 37 43-6=37 43−6=37 | 8 8 8 | 否 |
| 5 → 6 5 \to 6 5→6 | 5 | 6 | 5 5 5 | 38 38 38 | 43 − 5 = 38 43-5=38 43−5=38 | 0 0 0 | 是 |
4、核心结论👇
- 工程最早结束时间：由顶点6的 v e = 43 ve=43 ve=43确定，即43个时间单位。
- 关键活动： 1 → 3 1 \to 3 1→3、 3 → 2 3 \to 2 3→2、 2 → 5 2 \to 5 2→5、 5 → 6 5 \to 6 5→6（时间余量为0）。
- 关键路径： 1 → 3 → 2 → 5 → 6 1 \to 3 \to 2 \to 5 \to 6 1→3→2→5→6，总权值和为43，与工程总工期一致。
六、总结：AOE-网的核心价值 🌟
AOE-网通过量化活动依赖关系和时间参数分析，将工程管理从“经验驱动”转化为“数据驱动”。无论是建筑工程、软件开发还是项目调度，掌握关键路径分析都能帮助精准把控进度，避免因活动延误导致的全局风险。
💡 下期将拆解更多数据结构实战案例，欢迎关注～