用Python实现图(Graph)的拓扑排序算法

拓扑排序是一种用于有向无环图（DAG）的排序算法，它对图中的节点进行线性排序，使得在排序中，任意一对节点 u 和 v，如果存在一条从 u 到 v 的边，那么 u 在排序中出现在 v 之前。拓扑排序算法可以应用于依赖关系管理、任务调度等场景。

下面是使用 Python 实现图的拓扑排序算法的代码：

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 topological_sort_util(self, v, visited, stack):
        visited[v] = True

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

        stack.insert(0, v)

    def topological_sort(self):
        visited = [False] * self.num_vertices
        stack = []

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

        return stack

在以上代码中，我们首先定义了一个 Graph 类，它包含一个 defaultdict 类型的字典 graph 用于存储图的边和节点之间的关系。add_edge 方法用于添加图的边。topological_sort_util 是一个递归函数，用于实现深度优先搜索（DFS）来进行拓扑排序。topological_sort 方法是对图中的所有节点进行深度优先搜索，并最终返回排序结果。

下面是一个使用例子：

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)

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

以上例子中，我们创建了一个有向图，图中的节点从 0 到 5，add_edge 方法用于添加边。最后我们调用 topological_sort 方法进行拓扑排序，并打印排序结果。

输出结果为：

拓扑排序结果： [5, 4, 2, 3, 1, 0]

这是此图的一个有效的拓扑排序序列。

总结：拓扑排序是一种对有向无环图进行排序的算法，通过深度优先搜索来实现。以上是使用 Python 实现图的拓扑排序算法的代码和使用例子，希望对你理解拓扑排序算法有所帮助。