概念原理

它是对有向无环图的顶点排成一个线性序列。用顶点表示活动，用弧表示活动间的优先关系的有向图称为AOV网（Activity on Vertex Network）
应用场景：

• 表示工程的次序关系
• 判断一个层级结构的图是否存在循环引用

需要注意的是拓扑排序的结果并不是唯一的。

Python实现代码

collections是一个内置标准包，不需要安装
当有向图中无环时，也可利用深度优先遍历进行拓扑排序，因为图中无环，则由图中某点出发进行深度优先搜索遍历时，最先退出DFS函数的顶点即是初度为零的顶点，是拓扑有序序列中最后一个顶点。由此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序系列。
在下面的代码展示中，使用的stack.insert(0, v)语句使后进栈的点位于前面的位置，因此输出的就是正向的拓扑有序序列。

from collections import defaultdict

class Graph:
   def __init__(self, vertices):
       self.graph = defaultdict(list)  # 声明gragh是一个list，那gragh[]就是一个列表数组，实际上就是邻接表
       self.V = vertices

   """
   可以通过添加弧，建立邻接表
   """

   def addEdge(self, u, v):
       self.graph[u].append(v)  # 如果不使用defaultdict，这里将会出错

   def topologicalSortUtil(self, v, visited, stack):
       visited[v] = True
       for i in self.graph[v]:  # 遍历v节点邻接表
           if visited[i] == False:
               self.topologicalSortUtil(i, visited, stack)
       stack.insert(0, v)

   def topologicalSort(self):
       visited = [False] * self.V
       stack = []
       for i in range(self.V):
           if visited[i] == False:
               self.topologicalSortUtil(i, visited, stack)  # ????
       print(stack)


g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)

print("拓扑排序结果：")
g.topologicalSort()