python DAG拓扑排序

原文：http://blog.csdn.net/pandora_madara/article/details/26478385
在DAG中DFS中顶点的出栈顺序即逆拓扑序。
此算法最后用了反转

Paste_Image.png

def topological_sort(graph):
is_visit = dict((node, False) for node in graph)
li = []

def dfs(graph, start_node):

    for end_node in graph[start_node]:
        if not is_visit[end_node]:
            is_visit[end_node] = True
            dfs(graph, end_node)
    li.append(start_node)

for start_node in graph:
    if not is_visit[start_node]:
        is_visit[start_node] = True
        dfs(graph, start_node)

li.reverse()
return li

if name == 'main':
graph = {
'v1': ['v5'],
'v2': ['v1'],
'v3': ['v1', 'v5'],
'v4': ['v2', 'v5'],
'v5': [],
}
li = topological_sort(graph)
print(li)