拓扑排序与关键路径算法

拓扑排序是一种对有向无环图进行排序的算法，它将图中的节点按照它们的依赖关系进行排序，使得每个节点在排列中都在它的后继节点之前。拓扑排序可以用于解决很多问题，例如任务调度、编译顺序等。

关键路径算法是一种用于确定项目中关键任务的算法。它通过计算每个任务的最早开始时间和最晚开始时间，来确定哪些任务对项目的完成时间具有关键作用。关键路径算法可以帮助项目管理者确定项目的关键路径，从而更好地控制项目的进度。

以下是拓扑排序和关键路径算法的详细步骤：

1. 拓扑排序：
- 创建一个空列表result和一个空集合visited。
- 遍历图中的每个节点，对于每个未访问过的节点，调用dfs函数进行深度优先遍历。
- 在dfs函数中，对于当前节点，将其加入visited集合中，并遍历其所有的后继节点。
- 对于每个后继节点，如果它未被访问过，则递归调用dfs函数。
- 在递归返回时，将当前节点加入result列表中。
- 最后将result列表反转，即可得到拓扑排序的结果。

2. 关键路径算法：
- 对于每个任务，计算它的最早开始时间EST和最晚开始时间LST。
- 对于每个任务，计算它的最早完成时间EFT和最晚完成时间LFT。
- 对于每个任务，计算它的总浮动时间TF和自由浮动时间FF。
- 对于每个任务，如果它的TF为0，则它是关键任务。