1.拓扑排序的定义：
在图论中，拓扑排序指一个 有向无环图 中所有顶点的特定线性序列。每个经拓扑排序后得到的顶点序列，必定满足以下两个条件：
-
1.每个顶点出现且仅出现一次；
-
2.对于每一条有向边
A -> B，在序列中都必顶点有A在顶点B的前面。
2.拓扑排序实现思路：
拓扑排序思路非常简单。一般来说，拓扑排序有以下几个步骤组成：
-
1.在图中找到所有入度为0的点并输出；
-
2.将所有与该点相连的边删除，相连的点入度减1；
-
3.重复步骤1~2,直到没有任何点入度为0为止。
3.拓扑排序注意事项：
若图中没有点入度为0，但是程序并没有输出所有点，说明这张图有环。有环图是不能进行拓扑排序的！！！
以下图为例：
这张图中，入度集合为：{0, 2, 2, 2, 1}，所以首先输出1，随即入度集合变为：{x, 1, 1, 1, 2}。
然后程序扫不出入度为0的点，就会出现死循环。这是因为图中存在一个 2 -> 3 -> 4 -> 2 ... 的环，不符合拓扑排序的适用范围。。。
4.拓扑排序代码实现：
int n, m, a[N]; //n是节点数，m是边数，a[]用来存每个点的入度
vector<int> G[N], v; //G[]用来存每条边,v用来存答案集合
queue<int> q; //q相当于中转，将符合要求的点放进vector便于删点
bool topsort () {
for (int i = 1; i <= n; i ++) {
if (a[i] == 0) q.push (i);
} //循环找入度为0的点，加入队列存着。
while (!q.empty()) {
int t = q.front(); //取出队头元素
q.pop();
v.push_back (t); //将队头元素加入vector中
for (auto it = G[t].begin (); it != G[t].end (); it ++) { //枚举每条边
if (--a[*it] == 0) { //将所有跟t点有关的点入度减1
q.push (*it); //如果删去后该点入度也是0，加入队列
}
}
}
if (v.size() == n) { //答案集合里存了n个点，说明排序完成
for (auto it = v.begin (); it != v.end (); it ++) {
cout << *it << endl;
} //输出
return true;
} else { //如果不是n个点，说明不是有向无环图，返回逻辑假
return false;
}
}