数据结构笔记chapter06

6.4.5 有向无环图——描述表达式

1.有向⽆环图（DAG）

若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图（Directed Acyclic Graph）

2.DAG描述表达式

 

 Step 1：把各个 *** 作数不重复地排成⼀排

Step 2：标出各个运算符的⽣效顺序（先 后顺序有点出⼊⽆所谓）

Step 3：按顺序加⼊运算符，注意“分层”

Step 4：从底向上逐层检查同层的运算符是否可以合体

---

6.4.6 有向无环图——拓扑排序

1. AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)：

⽤DAG图（有向无环图）表示⼀个⼯程。

顶点表示活动，有向边表示活动Vi必须先于活动Vj进行

（AVO网不允许存在环路）

2. 拓扑排序：找到做事的先后顺序

（1）在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：

① 每个顶点出现且只出现⼀次。

② 若顶点A在序列中排在顶点B的前⾯，则在图中不存在从顶点B到顶点A的路径。

或定义为：拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后⾯。

每个AOV⽹都有⼀个或多个拓扑排序序列

（2）拓扑排序的实现：

① 从AOV网中选择⼀个没有前驱（⼊度为0）的顶点并输出。

② 从网中删除该顶点和所有以它为起点的有向边。

③ 重复①和②直到当前的AOV网为空  或  当前网中不存在无前驱的顶点为止（说明有回路）。

（当前所有顶点⼊度>0， 说明原图存在回路）

（3）代码实现

（待补）

时间复杂度：O(|V|+|E|) ，采用邻接表

若采⽤邻接矩阵，则需O(|V|^2)

3. 逆拓扑排序

对⼀个AOV⽹，如果采⽤下列步骤进⾏排序，则称之为逆拓扑排序：

① 从AOV⽹中选择⼀个没有后继（出度为0）的顶点并输出。

② 从⽹中删除该顶点和所有以它为终点的有向边。

③ 重复①和②直到当前的AOV⽹为空。

DFS逆拓扑排序实现：

在顶点退栈前输出

---

6.4.7 关键路径

1.AOE⽹

（1）在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如 完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹ (Activity On Edge NetWork)

（2）AOE⽹具有以下两个性质：

① 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；

② 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。

另外，有些活动是可以并行进行的

（3）在AOE⽹中仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始； 也仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，⽽把关键路径上的活动称为关键活动。

最大路径长度为完成整个工程的最小时间。

完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个 ⼯程的完成时间就会延⻓。

2.关键路径

例子：做番茄炒蛋

（1）最早：从前往后推

事件vk的最早发⽣时间ve(k)——决定了所有从vk开始的活动能够开⼯的最早时间

活动ai的最早开始时间e(i)——指该活动弧的起点所表⽰的事件的最早发⽣时间

（2）最迟：从后往前推

事件vk的最迟发⽣时间vl(k)——它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间。

活动ai的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差。

（3）活动ai的时间余量d(i)=l(i)-e(i)，表⽰在不增加完成整个⼯程所需总时间的情况下，活动ai可以拖延的时间

若⼀个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i) = e(i)的活动ai是关键活动 由关键活动组成的路径就是关键路径。

3. 求关键路径的步骤

① 求所有事件的最早发⽣时间 ve( )

按拓扑排序序列，依次求各个顶点的 ve(k):

ve(源点) = 0

ve(k) = Max{ve(j) + Weight(vj, vk)}, vj为vk 的任意前驱

这个活动前所有的准备活动都已经完成，所以要取Max

② 求所有事件的最迟发⽣时间 vl( ) ：

按逆拓扑排序序列，依次求各个顶点的 vl(k):

vl(汇点) = ve(汇点)

vl(k) = Min{vl(j) - Weight(vk, vj)} , vj为vk的任意后继

要求有足够的时间完成剩余活动，所以取min

③ 求所有活动的最早发⽣时间 e( )：

若边表⽰活动ai，则有e(i) = ve(k)

事件发生的最早时间，是弧尾（前驱结点）所连事件的最早发生时间

④ 求所有活动的最迟发⽣时间 l( )

若边表⽰活动ai，则有l(i) = vl(j) - Weight(vk, vj)

后继结点最晚发生时间减去边的权值

⑤ 求所有活动的时间余量 d( )

d(i) = l(i) - e(i)

d(k)=0的活动就是关键活动, 由 关键活动可得关键路径

4. 关键活动、关键路径的特性

（1）若关键活动耗时增加，则整个⼯程的⼯期将增⻓

（2）缩短关键活动的时间，可以缩短整个⼯程的⼯期

（3）当缩短到⼀定程度时，关键活动可能会变成⾮关键活动

（4）可能有多条关键路径，只提⾼⼀条关键路径上的关键活动速度并不能缩短整个⼯程的⼯ 期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短⼯期的⽬的。