如何使用Python实现拓扑排序的算法逻辑

拓扑排序是一种对有向无环图（DAG）进行排序的算法。在拓扑排序中，图中的节点代表任务，有向边代表任务之间的依赖关系。按照拓扑排序的结果，图中的节点可以按照一种线性序列来执行，同时满足所有的依赖关系。

下面是使用Python实现拓扑排序的算法逻辑的代码：

from collections import defaultdict

def topologicalSort(graph):
    # 创建一个字典来记录每个节点的入度
    inDegree = defaultdict(int)

    # 遍历图中的每个节点，统计每个节点的入度
    for node in graph:
        neighbors = graph[node]
        for neighbor in neighbors:
            inDegree[neighbor] += 1

    # 创建一个队列，用于存储入度为0的节点
    queue = []

    # 将入度为0的节点加入队列
    for node in graph:
        if inDegree[node] == 0:
            queue.append(node)

    result = []
    # 循环遍历队列中的节点，直到队列为空
    while queue:
        # 弹出队列中的节点
        node = queue.pop(0)
        result.append(node)

        # 更新与该节点邻接节点的入度
        neighbors = graph[node]
        for neighbor in neighbors:
            inDegree[neighbor] -= 1
            # 如果邻接节点的入度为0，则加入队列
            if inDegree[neighbor] == 0:
                queue.append(neighbor)

    # 如果所有节点都被访问过，说明拓扑排序成功
    if len(result) == len(graph):
        return result
    else:
        return []

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

sorted_result = topologicalSort(graph)
if sorted_result:
    print("拓扑排序结果：", sorted_result)
else:
    print("图中存在环，无法进行拓扑排序")

在上面的代码中，首先创建了一个字典inDegree用于记录每个节点的入度。然后遍历图中的每个节点，统计每个节点的入度。

接下来创建一个队列queue，用于存储入度为0的节点。将入度为0的节点加入队列。然后循环遍历队列中的节点，弹出节点并将其加入结果列表result中。同时更新与弹出节点邻接的节点的入度，并将入度为0的邻接节点加入队列。

最后，判断结果列表中的节点数是否等于图中的节点数。如果相等，说明拓扑排序成功，返回结果列表。否则，说明图中存在环，无法进行拓扑排序，返回空列表。

在以上的示例中，图的节点为'A', 'B', 'C', 'D'，边表示节点之间的依赖关系。节点'A'依赖于节点'B'和节点'C'，节点'B'依赖于节点'C'和节点'D'，节点'C'依赖于节点'D'。最终的拓扑排序结果为'D', 'C', 'B', 'A'。