递归实现拓扑排序python

可以使用深度优先搜索（DFS）算法对有向无环图（DAG）进行拓扑排序。先进行DFS遍历，对于每个节点，记录其访问状态，分为三种：未访问、正在访问和已访问。每当遍历到一个节点时，将其状态设置为正在访问，然后对其所有未访问的邻居进行DFS遍历。如果邻居节点已经被访问过了，则说明存在环，直接return。当所有邻居节点都被访问过后，将该节点状态设置为已访问，并将其加入结果列表中。最后逆序输出结果列表即可得到拓扑排序结果。

以下是递归实现的Python代码：

from collections import defaultdict

def topoSort(node, graph, visited, result):
    visited[node] = 1
    for neighbor in graph[node]:
        if visited[neighbor] == 0:
            topoSort(neighbor, graph, visited, result)
        elif visited[neighbor] == 1:
            # 如果邻居节点已经被访问过了，说明存在环，直接return
            return
    visited[node] = 2
    result.append(node)

def topoSortDFS(graph):
    visited = defaultdict(int)
    result = []

    for node in graph.keys():
        if visited[node] == 0:
            topoSort(node, graph, visited, result)

    return result[::-1]

其中，graph为邻接表表示的有向无环图。结果列表中的节点顺序即为拓扑排序后的结果。