拓扑排序与关键路径算法

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

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

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

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

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

相关问题

拓扑排序 ,关键路径算法代码

拓扑排序是一种对有向无环图进行排序的算法，它将图中的所有结点排成一个线性序列，使得图中任意一对顶点和v，若边(u,v)∈E，则u在线性序列中出现在v的前面。关键路径算法是一种用来确定工程中各个活动的最长时间或最短时间的方法，它是基于拓扑排序的。

以下是拓扑排序的Python代码实现：

def topological_sort(graph):
    in_degree = dict((u, 0) for u in graph)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    queue = [u for u in graph if in_degree[u] == 0]
    result = []
    while queue:
        u = queue.pop(0)
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    if len(result) != len(graph):
        return None # 存在环
    return result

以下是关键路径算法的Python代码实现：

def critical_path(graph, source, sink):
    def dfs(v):
        visited.add(v)
        if v == sink:
            return
        for u, w in graph[v]:
            if u not in visited:
                dfs(u)
            dist[v] = max(dist[v], dist[u] + w)
        topological_order.append(v)

    visited = set()
    topological_order = []
    dist = {v: 0 for v in graph}
    dfs(source)
    critical_path_length = dist[sink]
    critical_path = []
    while topological_order:
        v = topological_order.pop()
        if dist[v] == critical_path_length:
            critical_path.append(v)
            critical_path_length -= max(w for u, w in graph[v])
    return critical_path[::-1], dist[sink]

拓扑排序关键路径算法

拓扑排序关键路径算法是一种用于确定有向无环图中关键路径的算法。其基本思想是通过拓扑排序来确定每个节点的最早开始时间和最晚开始时间，从而计算出每个活动的最早开始时间、最晚开始时间和总时差，从而确定关键路径。

算法流程如下：
1. 对有向无环图进行拓扑排序，得到每个节点的最早开始时间。
2. 从起点开始，按照拓扑序列依次计算每个节点的最晚开始时间。
3. 计算每个活动的最早开始时间、最晚开始时间和总时差。
4. 根据总时差为0的活动确定关键路径。

下面是一个简单的例子，假设有以下有向无环图：

A --> B --> C --> D
 \            /
   --> E -->

其中，A、B、C、D、E分别表示节点，箭头表示有向边。假设每个节点的执行时间如下：

A: 2
B: 3
C: 4
D: 2
E: 1

则按照上述算法流程，可以得到以下结果：

1. 进行拓扑排序，得到拓扑序列为A -> E -> B -> C -> D。
2. 从起点A开始，按照拓扑序列依次计算每个节点的最晚开始时间，得到以下结果：
- A: 最晚开始时间为2
- E: 最晚开始时间为2
- B: 最晚开始时间为5
- C: 最晚开始时间为9
- D: 最晚开始时间为11
3. 计算每个活动的最早开始时间、最晚开始时间和总时差，得到以下结果：
- A -> B: 最早开始时间为2，最晚开始时间为5，总时差为3
- A -> E: 最早开始时间为2，最晚开始时间为2，总时差为0
- B -> C: 最早开始时间为5，最晚开始时间为9，总时差为4
- C -> D: 最早开始时间为9，最晚开始时间为11，总时差为2
- E -> B: 最早开始时间为2，最晚开始时间为5，总时差为3
- E -> C: 最早开始时间为3，最晚开始时间为6，总时差为3
4. 根据总时差为0的活动确定关键路径，即A -> E。