数据结构拓扑排序代码

数据结构中的拓扑排序，通常是针对有向无环图（DAG，Directed Acyclic Graph）的，用于确定节点之间的依赖顺序。这种排序可以应用于任务调度、课程安排等场景，其中每个节点代表一个事件，边表示事件间的依赖关系。

以下是使用Python实现一个简单的拓扑排序算法的例子：

from collections import defaultdict

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}  # 初始化入度为0
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1  # 计算每个节点的前驱节点数

    queue = [node for node in in_degree if in_degree[node] == 0]  # 创建队列，优先级低的先出队
    sorted_nodes = []

    while queue:
        node = queue.pop(0)  # 出队头节点
        sorted_nodes.append(node)

        for neighbor in graph[node]:  # 更新相邻节点的入度
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(sorted_nodes) != len(graph):  # 如果所有节点都已处理，说明是无环图
        return "Graph contains a cycle and is not DAG"
    else:
        return sorted_nodes  # 返回排序后的节点列表

# 示例：
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}
print(topological_sort(graph))  # 输出：['C', 'A', 'B', 'D']

在这个例子中，`graph`是一个字典，键是节点名，值是一个包含直接依赖的子节点列表。算法首先计算每个节点的入度，然后将入度为0的节点放入队列。每次从队列中取出一个节点并添加到结果列表，同时更新其相邻节点的入度。如果最后所有的节点都被处理过，那么返回的列表就是有效的拓扑排序；如果有未处理的节点，说明存在循环，图不是无环图。