拓扑排序有环关键路径

拓扑排序是一种对有向无环图（DAG）进行排序的算法，它将图中的节点按照依赖关系进行排序。如果图中存在环，即存在循环依赖关系，则无法进行拓扑排序。

关键路径是指在一个有向加权图中，从起点到终点的最长路径。关键路径上的任务不允许延迟，否则会影响整个项目的进度。

在拓扑排序中，如果存在环，则无法确定节点之间的依赖关系，因此无法计算关键路径。而在计算关键路径时，通常使用网络图的拓扑排序作为基础，因为只有在没有环的情况下才能计算出有效的关键路径。

相关问题

拓扑排序 2、关键路径

拓扑排序是一种对有向无环图进行排序的算法，它将图中的所有节点排成一个线性序列，使得对于任何的有向边 (u, v)，在序列中节点 u 都排在节点 v 的前面。拓扑排序可以用来判断一个有向图是否有环，如果有环，则无法进行拓扑排序。

关键路径是指在一个有向无环图中，从源点到汇点的所有路径中，耗时最长的路径称为关键路径。关键路径上的任务必须按照顺序依次执行，否则整个工程的进度就会受到影响。因此，关键路径的长度决定了整个工程的最短完成时间。

举个例子，假设有一个工程包含多个任务，每个任务都有一个耗时，任务之间存在依赖关系，即某些任务必须在其他任务完成后才能开始。我们可以将这些任务看作有向图中的节点，任务之间的依赖关系看作有向边，然后使用拓扑排序算法来确定任务的执行顺序，再使用关键路径算法来确定整个工程的最短完成时间。

拓扑排序与关键路径算法

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

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

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

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

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