一、拓扑排序 含义
构造AOV网络全部顶点的拓扑有序序列的运算称为拓扑排序(Topological Sorting)。
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。
且该序列必须满足下面两个条件：
①每个顶点出现且只出现一次。
②若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
注：有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
二、Kahn 算法
方法步骤：
①从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
②从图中删除该顶点和所有以它为起点的有向边。
重复 ① 和 ② 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。（后一种情况说明有向图中存在环。）
代码实现：
int du[N];
queue <int> q;
void topsort() {
for(int i = 1;i <= n;i ++) if(! du[i]) q.push(i);
while(! q.empty()) {
int tp = q.front(); q.pop();
for(int i = head[tp]; i ;i = e[i].nxt) {
du[e[i].to] --;
if(! du[e[i].to]) q.push(e[i].to);
}
}
}
三：基于DFS的求解方法
思想方法：
Dfs时候，遇到u->v边，通过在Dfs函数快退出时将结点加入到容器中实现v在序列的位置始终在u的前
代码实现：
void Dfs(int x) {
vis[x] = 1;
for(int i = head[x]; i ;i = e[i].x)
if(!vis[e[i].to]) Dfs(edge[k].to);
ans.push_back(x);
}