【图】描述表达式+拓扑排序+关键路径_设计算法实现以逆邻接表

有向无环图描述表达式

有向无环图（走不回来的有向图）

DAG描述表达式

解决计算过程中有多处重复计算的方法和存储结构

实例方法演示

---

---

1. 总之，合并重复结果，删除多余节点
2. 由于运算顺序的不唯一性，故生成的图结果不唯一

---

拓扑排序（找到做事的先后顺序）

AOV网

拓扑排序的实现

• 从AOV网中选择一个没有前驱（入度为0)的顶点并输出。
• ②从网中删除该顶点和所有以它为起点的有向边。
• ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（说明有回路）。

Code

---

复杂度分析

逆拓扑排序

---

逆邻接表

逆邻接表：记录结点的入度边的信息

逆拓扑排序的实现(DFS算法)

1. 拓扑排序、逆拓扑排序序列可能不唯一
2. 若图中有环，则不存在拓扑排序序列/逆拓扑排序序列

---

关键路径

AOE网

---

---

关键路径

求解关键路径

实例演示

---

---

---

---

---

---

---

结果分析

关键路径和活动的特性

1. 若关键活动耗时增加，则整个工程的工期将增长，缩短关键活动的时间，可以缩短整个工程的工期
2. 当缩短到一定程度时，关键活动可能会变成非关键活动
3. 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。