如何实现图的拓扑排序

拓扑排序是对有向无环图(DAG)进行排序的一种算法。它可以用来解决很多实际问题，比如依赖关系的排序、任务调度等。

拓扑排序的基本思想是：将图中所有节点按照依赖关系排序，使得每个节点都排在它的后继节点之前。

具体实现步骤如下：

1. 统计每个节点的入度（即指向该节点的边的数量）。

2. 将所有入度为 0 的节点加入到一个队列中。

3. 从队列中取出一个节点，将其输出到结果序列中，并将其所有后继节点的入度减 1。

4. 如果某个后继节点的入度变为 0，则将其加入到队列中。

5. 重复步骤 3 和 4，直到队列为空为止。

如果图中存在环路，则无法进行拓扑排序。

下面是一个示例代码实现：

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    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]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(graph):
        raise ValueError("Graph contains a cycle")

    return result

其中，`graph` 是一个字典，表示图的邻接表形式。例如，`graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}` 表示图中有四个节点，A 依赖于 B 和 C，B 依赖于 D，C 也依赖于 D，D 没有后继节点。