AOV（Activity On Vertex）和 AOE（Activity On Edge）是两种常用于工程计划与调度中的有向图模型，主要用于表示任务之间的依赖关系和时间安排。它们都属于关键路径法（Critical Path Method, CPM）和项目评审技术（Program Evaluation and Review Technique, PERT）中的基本建模工具。

下面分别介绍它们的定义、特点、用途及区别：

---

一、AOV 网（Activity On Vertex Network）

1. 定义

• 顶点（Vertex）表示活动（Activity）
• 有向边（Directed Edge）表示活动之间的先后关系（即偏序关系）
• 若存在一条从顶点 A 到顶点 B 的有向边，则表示活动 A 必须在活动 B 之前完成

2. 特点

• 不考虑活动所需的时间（或默认时间为1）
• 主要用于判断活动安排是否合理（即是否存在循环依赖）
• 核心操作是拓扑排序（Topological Sorting）

3. 应用场景

• 课程先修关系（如“数据结构”必须在“算法设计”之前）
• 编译依赖（模块编译顺序）
• 任务调度中的依赖检查

4. 关键问题

• 是否存在环？若有环，则无法进行拓扑排序，说明安排不合理。
• 能否生成一个合法的执行顺序？→ 拓扑序列

---

二、AOE 网（Activity On Edge Network）

1. 定义

• 边（Edge）表示活动
• 顶点（Vertex）表示事件（Event），即某个或某些活动的开始或结束时刻
• 每条边有权重，表示该活动所需的持续时间
• 通常只有一个源点（入度为0，表示工程开始）和一个汇点（出度为0，表示工程结束）

2. 特点

• 强调时间和关键路径
• 可用于计算：
  • 整个工程的最短完成时间
  • 每个活动的最早开始时间（earliest start time）
  • 每个活动的最晚开始时间（latest start time）
  • 关键活动（总时差为0的活动）和关键路径

3. 应用场景

• 工程项目管理（如建筑、软件开发）
• 估算项目工期
• 识别哪些活动不能延误（关键路径上的活动）

4. 关键概念

• 关键路径：从源点到汇点的最长路径（因为边权是时间，路径越长，总工期越长）
• 事件的最早发生时间（ve）：从源点到该事件的最长路径长度
• 事件的最迟发生时间（vl）：在不影响总工期的前提下，该事件最晚发生时间
• 活动的最早开始时间 e(i) = ve(起点)
• 活动的最晚开始时间 l(i) = vl(终点) – 活动持续时间
• 时差 = l(i) – e(i)，若为0，则为关键活动

---

三、AOV 与 AOE 的主要区别

表格

项目	AOV 网	AOE 网
活动表示	顶点	边
事件/状态	无显式事件	顶点表示事件
边的含义	依赖关系（无权重）	活动本身（带权重=时间）
是否带权	否	是
主要目的	检查依赖合理性、拓扑排序	计算工期、找关键路径
是否允许环	不允许（否则无法拓扑排序）	不允许（否则工期无限）
典型算法	拓扑排序、检测环	关键路径算法（基于拓扑序计算 ve/vl）

---

四、小结

• AOV 关注“谁先谁后”，用于逻辑依赖分析
• AOE 关注“花多少时间”，用于时间与资源优化

两者常常结合使用：先用 AOV 确保任务依赖无环，再构建 AOE 网进行工期分析。