本文主要是介绍DAG图的拓扑排序 python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在DAG中DFS中顶点的出栈顺序即逆拓扑序。
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] = Truedfs( graph, end_node )li.append( start_node )for start_node in graph:if not is_visit[start_node]:is_visit[start_node] = Truedfs( graph, start_node )li.reverse()return liif __name__ == '__main__':graph = {'v1': ['v5'],'v2': ['v1'],'v3': ['v1', 'v5'],'v4': ['v2', 'v5'],'v5': [],}li = topological_sort( graph )print li
这篇关于DAG图的拓扑排序 python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
