数据结构-有向无环图的拓扑排序代码实现

在数据结构中，有向无环图（DAG，Directed Acyclic Graph）的拓扑排序是一种将顶点按照一定顺序排列的方式，满足对于每条有向边 (u, v)，顶点 u 的排列位置都在 v 之前。以下是使用 Python 实现的一个简单拓扑排序算法：

from collections import deque

def is_dag(graph):
    visited = set()
    for node in graph:
        if node not in visited and has_cycle(node, graph, visited):
            return False
    return True

def has_cycle(node, graph, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited and has_cycle(neighbor, graph, visited):
            return True
    visited.remove(node)
    return False

def topological_sort(graph):
    if not is_dag(graph):
        raise ValueError("Graph contains a cycle and cannot be sorted.")

    indegree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1

    queue = deque([node for node in graph if indegree[node] == 0])
    
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == len(graph) else None

# 示例使用
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

sorted_nodes = topological_sort(graph)
print(f"Toplevel nodes: {sorted_nodes}")

在这个代码中，`is_dag`函数检查图是否无环，`topological_sort`函数首先计算每个节点的入度并创建一个队列，然后依次取出入度为0的节点添加到结果中，并更新相邻节点的入度。如果最终得到的结果等于图中的节点数，则说明成功完成排序，否则说明图中存在环。