数据结构拓扑排序算法代码

拓扑排序是针对有向无环图（DAG）的一种排序算法，它会返回一个顺序列表，表示图中节点的线性顺序，这个顺序满足图中所有有向边的“方向”，即如果存在一条从节点A指向节点B的边，那么在排序中A一定出现在B之前。

拓扑排序算法的常见实现是基于深度优先搜索（DFS）的。下面是一个用Python编写的拓扑排序的示例代码：

from collections import defaultdict

# 定义图数据结构
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)  # 用字典存储图结构，键为节点，值为邻接点列表
        self.V = vertices  # 图中顶点的数量

    # 添加边到图中
    def add_edge(self, u, v):
        self.graph[u].append(v)

    # 拓扑排序算法
    def topological_sort(self):
        stack = []  # 用来存放所有入度为0的顶点

        # 初始化所有顶点的入度为0
        in_degree = [0] * (self.V)

        # 计算所有顶点的入度
        for i in self.graph:
            for j in self.graph[i]:
                in_degree[j] += 1

        # 将所有入度为0的顶点入栈
        for i in range(self.V):
            if in_degree[i] == 0:
                stack.append(i)

        # 用于存储拓扑排序的结果
        top_order = []

        # 重复下列步骤直到栈为空
        while stack:
            # 弹出一个顶点
            i = stack.pop()
            top_order.append(i)

            # 减少所有邻接点的入度
            for node in self.graph[i]:
                in_degree[node] -= 1
                # 如果入度减为0，则入栈
                if in_degree[node] == 0:
                    stack.append(node)

        return top_order

# 示例使用拓扑排序算法
if __name__ == '__main__':
    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())

这段代码首先定义了一个图类，包含了添加边和拓扑排序的方法。`topological_sort`方法中，使用了一个栈来存储所有入度为0的节点，并通过不断地弹出这些节点，并更新邻接节点的入度，最后得到拓扑排序的结果。