算法详解：有向无环图（DAG）拓扑排序算法

算法一：

寻找入度为0（没有任何结点指向它）的结点Q，删除Q及与Q相连的边。

重复上述操作直到结点被全部删除，或找不到入度为0的结点（存在有向环，非DAG）。

算法二：

遍历每一个结点，通过DFS访问结点的所有子孙。当前结点无子孙时为递归边界，将结点加入到当前拓扑序的首部。

需要注意的是，要判断递归路上是否有遇到存在有向环的结点，故要用\(vis[u]\)存储结点状态：

\(vis[u]=0\)时，结点\(u\)从未访问过；

\(vis[u]=-1\)时，结点\(u\)正在访问；

\(vis[u]=1\)时，结点\(u\)已访问完毕。

算法详解：有向无环图（DAG）拓扑排序算法

原文：https://www.cnblogs.com/streamazure/p/12664250.html