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

拓扑排序是一种对有向无环图进行排序的算法，它将图中的所有结点排成一个线性序列，使得图中任意一对顶点和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]