有向有环图进行排序的算法(拓扑法)

使用拓扑法对节点之间的连接关系进行排序

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。

def topologicalSort(graph):
    def dfs(node):
        record.add(node)  # 3. 记录当前访问节点
        # 4. 递归遍历当前节点的所有出边的终点节点(从该节点流出后流向的节点)。
        for adjacency_node in graph[node]:
            if adjacency_node not in visited:
                dfs(adjacency_node)
        stack.append(node)  # 5. 当前节点入栈

    stack = []  
    # 1. record保存已经访问过的节点
    record= set()   
    # 2. 遍历每个节点，若节点未访问， 则调用dfs函数进行深度优先搜索
    for node in graph:  
        if node not in record:
            dfs(node)
    return stack[::-1]  # 6. 栈中的节点依次出栈(顺序)

graph = {
    "A1": ["B"],
    'A': ['B', 'C'],
    'B': ['C', 'D'],
    'C': ['D'],
    'D': ['C', 'E'],
    'E': []
}
result = topologicalSort(graph)
print(result)  # 输出：['A', 'A1', 'B', 'C', 'D', 'E']