biscuitの博客

利用AOV网的拓扑排序算法#

基本思想：

1. 选出一个没有前驱的顶点，将其输出到拓扑序列中。

2. 从图中删除该顶点及其所有出边。

3. 重复上述步骤，直到所有顶点都被输出或图中不存在没有前驱的顶点。

NOTE

如果图中仍有顶点未被输出，但不存在没有前驱的顶点，则说明图中存在环，无法进行拓扑排序。

拓扑排序只是DAG的一种线性表示方式，DAG可能有多个不同的拓扑排序结果。

Kahn算法（队列）#

1. 计算图中每个顶点的入度。

2. 初始化一个队列，将所有入度为0的顶点加入队列。

3. 初始化一个空的拓扑序列。

4. 当队列不为空时，执行以下操作：

   • 从队列中取出一个顶点u，将其加入拓扑序列。

   • 对于u的每个邻接顶点v，减少v的入度。如果v的入度变为0，则将v加入队列。

利用DFS的拓扑排序算法（栈）#

1. 初始化一个空的栈和一个访问标记数组。

2. 对图中的每个顶点执行以下操作：

   • 如果该顶点未被访问，则调用DFS函数。
   • 在DFS函数中，标记当前顶点为已访问，递归访问其所有未被访问的邻接顶点。
   • 在所有邻接顶点都被访问后，将当前顶点压入栈中。

3. 最后，从栈中依次弹出顶点，得到拓扑序列。

CPM的数据结构#

AOE网：有向图，顶点表示事件，边表示事件依赖的活动以及持续时间。

事件 $V_j$ 的最早发生时间 $VE[j]$ ：表示事件 $V_j$ 可以最早发生的时间。

事件 $V_j$ 的最晚发生时间 $VL[j]$ ：表示事件 $V_j$ 可以最晚发生的时间。

活动 $A_{ij}$ 的最早开始时间 $E[i][j]$ ：表示活动 $A_{ij}$ 可以最早开始的时间。

如果活动 $A_{ij}$ 恰好在边 $(V_i,V_j)$ 上进行，则有 $E[i][j] = VE[i]$ 。

活动 $A_{ij}$ 的最晚开始时间 $L[i][j]$ ：表示活动 $A_{ij}$ 可以最晚开始的时间。

如果活动 $A_{ij}$ 恰好在边 $(V_i,V_j)$ 上进行，则有 $L[i][j] = VL[j] - w(i,j)$ 。

关键路径上的活动：对于活动 $A_{ij}$，如果满足 $E[i][j] = L[i][j]$，则称该活动为关键活动，关键路径由所有关键活动组成。