数据结构关键路径问题求解代码

关键路径问题是一个经典的工程问题，可以使用AOV网和拓扑排序来解决。以下是求解关键路径问题的Python代码：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True
        if v in self.graph.keys():
            for node, weight in self.graph[v]:
                if not visited[node]:
                    self.topological_sort_util(node, visited, stack)
        stack.append(v)

    def topological_sort(self):
        visited = {v: False for v in self.V}
        stack = []
        for v in self.V:
            if not visited[v]:
                self.topological_sort_util(v, visited, stack)
        return stack[::-1]

    def longest_path(self, start, end):
        dist = {v: float('-inf') for v in self.V}
        dist[start] = 0
        top_order = self.topological_sort()
        for u in top_order:
            if u == end:
                return dist[end]
            if dist[u] != float('-inf'):
                for v, w in self.graph[u]:
                    if dist[v] < dist[u] + w:
                        dist[v] = dist[u] + w

# 示例
g = Graph(['a', 'b', 'c', 'd', 'e'])
g.add_edge('a', 'b', 3)
g.add_edge('a', 'c', 2)
g.add_edge('b', 'd', 5)
g.add_edge('c', 'd', 7)
g.add_edge('d', 'e', 4)
print("关键路径长度为：", g.longest_path('a', 'e'))

上述代码中，我们首先定义了一个Graph类，其中包含了AOV网的构建、拓扑排序和关键路径长度的计算。在构建AOV网时，我们使用了Python的defaultdict来存储图的邻接表。在拓扑排序中，我们使用了DFS算法，并将访问过的节点压入栈中。在计算关键路径长度时，我们使用了动态规划的思想，依次计算每个节点的最长路径，并返回终点的最长路径。