拓扑排序什么是拓扑序列
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：
若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。
设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。
比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。
注意：
①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
②若图中存在有向环，则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。
昨天花了一天的时间研究了下拓扑排序，觉得学到很多，所以写一下总结。
<1>有向图的表示方式可以分成邻接矩阵和邻接表两种。
邻接矩阵是指用一个n*n的数组，下标为i,j的位置记录点i和点j的关系。（适用与稀疏矩阵，对内存空间要求要比较高）
邻接表是单纯记录关系的数组，比如 i和 j 有关系， 就将 j 放在 [i][k]的位置（k为当前与i有关系的点数），这种表示法适用于关系较少的时候，但是引用进STL中的vector以后，好像数据量的大小对其就没有什么太大的影响了。
<2>拓扑排序：每次找到入度为0 的点，并将其出度清空（可以用DFS或BFS），跟据表示的方法不同，操作也会有所差别。
<3>给出有向图之后，会有存在拓扑排序和不存在拓扑排序之分，如果图中存在有向环，则不存在拓扑排序（就是在遍历的过程中直接和间接的相互指向），在处理上只要记录每个点的访问状态就可以了，是正在访问（不满足的情况），还是未访问，或是已经访问过（DFS)。
如果存在了拓扑排序，也会有拓扑排序唯不唯一的问题（如果没有要求考虑这点，用DFS会号做一些），这点其实也好处理，只要每次入度为0的点只有一个才可以（BFS）。
DFS + 邻接表
DFS + 邻接矩阵。
int vis[MAXN];
int topo[MAXN], cnt;
bool DFS(int u){
vis[u] = -1; //表示当前正在访问，如果再次访问说明不存在topo排序。
for (int i = 0; i < n; i++){
if (G[u][i]){
if (vis[i] < 0)
return false; //存在有向环，失败退出。
else if (!vis[i] && !DFS(i))
return false;
}
}
vis[u] = 1;
topo[--cnt] = u;
return true; // 成功记录，返回true 。
}
bool toposort(){
cnt = n;
memset(vis, 0, sizeof(vis)); // 如果要考虑排序是否唯一，这边每次都需将所有点遍历过一遍，且每次只可有一点的入度为0。
for (int u = 0; u < n; u++)
if (!DFS(u))
return false;
return true;
}
// DFS + 邻接矩阵。
int vis[MAXN];
int topo[MAXN], cnt;
bool DFS(int u){
vis[u] = -1; //表示当前正在访问，如果再次访问说明不存在topo排序。
for (int i = 0; i < n; i++){
if (G[u][i]){
if (vis[i] < 0)
return false; //存在有向环，失败退出。
else if (!vis[i] && !DFS(i))
return false;
}
}
vis[u] = 1;
topo[--cnt] = u;
return true; // 成功记录，返回true 。
}
bool toposort(){
cnt = n;
memset(vis, 0, sizeof(vis)); // 如果要考虑排序是否唯一，这边每次都需将所有点遍历过一遍，且每次只可有一点的入度为0。
for (int u = 0; u < n; u++)
if (!DFS(u))
return false;
return true;
}BFS(借助STL-queue) + 邻接表（借助STL-vector)
// BFS + 邻接表。
vector G[MAXN]; // 邻接表。
int son[MAXN]; // 入度数。
void topo(){
queue que;
int ok = 0;
for (int i = 0; i < n; i++)
if (!son[i])
que.push(i); // 入度为0时入队。
while (!que.empty()){
if (que.size() > 1)
ok = 1; // 当队列中个数超多1时，表示有不唯一解。
int t = que.front();
que.pop();
cnt--; // 如果队列为空后，计数器> 0， 说明存在环结构。
for (int i = 0; i < G[t].size(); i++)
if (--son[G[t][i]] == 0) // 判断减掉当前点的关系后，点的入度是否为0。
que.push(G[t][i]);
}
}