python实现拓扑排序

拓扑排序是一种对有向无环图（DAG）进行排序的算法。在Python中，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现拓扑排序。

以下是使用深度优先搜索（DFS）算法实现拓扑排序的示例代码：

from collections import defaultdict

# 定义有向图的类
class Graph:
    def __init__(self, num_vertices):
        self.graph = defaultdict(list)  # 使用字典存储图的邻接表
        self.num_vertices = num_vertices

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

    # 深度优先搜索函数
    def dfs(self, v, visited, stack):
        visited[v] = True

        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                self.dfs(neighbor, visited, stack)

        stack.append(v)

    # 拓扑排序函数
    def topological_sort(self):
        visited = [False] * self.num_vertices
        stack = []

        for vertex in range(self.num_vertices):
            if not visited[vertex]:
                self.dfs(vertex, visited, stack)

        return stack[::-1]  # 返回逆序的结果

# 测试示例
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

result = g.topological_sort()
print("拓扑排序结果：", result)

这段代码首先定义了一个有向图的类 `Graph`，其中包含了添加边、深度优先搜索和拓扑排序的方法。在测试示例中，创建了一个有向图实例 `g`，并添加了6个顶点和相应的边。然后调用 `topological_sort` 方法进行拓扑排序，并将结果打印出来。

希望这段代码能够帮助到你理解如何在Python中实现拓扑排序算法。