拓扑排序中的邻接表表示

拓扑排序是一种对有向无环图进行排序的算法，其中邻接表表示是一种常用的图表示方法。下面是一个使用邻接表表示图并进行拓扑排序的代码示例：

from collections import defaultdict

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = defaultdict(list)  # 邻接表

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

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True

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

        stack.append(v)

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

        for v in range(self.num_vertices):
            if not visited[v]:
                self.topological_sort_util(v, 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)

输出结果为：[5, 4, 2, 3, 1, 0]，表示拓扑排序的结果。

在示例代码中，首先定义了一个Graph类，其中num_vertices表示图中顶点的数量，adj_list是一个字典，用于存储每个顶点的邻接顶点。然后，add_edge方法用于向图中添加边。

topological_sort_util是一个递归函数，用于进行深度优先搜索，并将访问过的顶点添加到栈中。topological_sort方法首先创建了一个visited数组，用于记录每个顶点是否被访问过，然后对每个未被访问过的顶点调用topological_sort_util函数。

最后，通过创建一个Graph对象，添加边，然后调用topological_sort方法，即可得到拓扑排序的结果。