定义
拓扑排序是图G的所有节点的一种线性次序，该次序满足下列条件：如果图G包含边(u,v),
则节点u在拓扑排序中处于节点v的前面(如果图G中包含环路，则不可能排出一个线性次序)。
也可以说，u,v之间存在一条可达路径，则u的拓扑序在v的前面。
算法实现
DFS
发现时间 d：该节点第一次被发现。
完成时间 f：该节点所有的可达节点都被发现。
使用DFS对有向无环图进行深度优先搜索,如果u.f < v.f，则在拓扑排序中u在v之前。
严谨的证明可以参考算法导论，不严谨的证明如下：如果v.f > u.f 则可以证明，图中存在一条v->u的可达路径，因为只有将v节点的所有可达节点都完成后，才会标记v的完成时间，
该时间一定比u的标记时间晚，也即是v.f > u.f;参考上面关于拓扑排序 的定义，(完成时间)--> (u,v 之间存在路径)-->(u,v之间的拓扑序)可以知道，通过完成时间，我们可以确定
拓扑顺序，即完成时间越晚，拓扑序越靠前。
实现
代码中，当一个点的所有节点被发现，也即是该节点已完成，则根据完成时间与拓扑序关系，将其放入拓扑排序的数组里。
使用vector建立邻接表。
vector<int> nod[101];
int n;
int vis[101];//存放访问的时间
int order[101];//存放拓扑排序的顺序
int t = 0;
int num;
void dfs(int s)
{
stack<int> st;
st.push(s);
vis[s] = ++t;
while(!st.empty())
{
int now = st.top();
int len = nod[now].size();
int id;
bool has = false;
for(int i = 0; i < len; ++i)
{
id = nod[now][i];
if(vis[id] == 0)
{
st.push(id);
vis[id] = ++t;
has = true;
break;
}
}
if(!has)
{
st.pop();
order[num--] = now;
}
}
}
kahn算法
集合S保存所有入度为零的点
1.如果集合S为空，算法结束，否则：从所有节点中选出入度为零的点加入集合S.(可根据需要对集合S进行排序)
2.从集合S中取出入度为零的点u，放入已确定拓扑序的节点序列末尾。遍历点u 的所有相邻边，对可达节点入度减一。如果可达节点入度为零，则加入集合S.
3.回到1.
算法结束后，如果此时检测所有点的的入度，存在入度不为零的点，则说明图中存在环路。
可以理解为，如果入度为零，根据拓扑排序的定义。则不存在拓扑序更靠前的点，则该节点的拓扑序可以确定。
实现
使用vector存放邻接表。
vector<int> nod[27];
int n,m;
int order[27];
int in[27];
int t = 0;
int num;
int topoSort(){
int ret = 1;
memset(vis,0,sizeof(vis));
memset(order,0,sizeof(order));
num = 0;
queue<int> q;
for(int i = 1; i <= n; ++i){
if(in[i] == 0)
{
q.push(i);
}
}
while(!q.empty()){
int now = q.front();
q.pop();
int len = nod[now].size();
for(int i = 0; i < len; ++i)
{
--in[nod[now][i]];
if(in[nod[now][i]] == 0)
{
q.push(nod[now][i]);
}
}
order[++num] = now;
}
for(int i = 1; i <= n; ++i)//存在入度不为零的点，存在环路，则拓扑排序不存在 。
{
if(in[i] != 0)
{
ret = -1;
}
}
return ret;
}
例题
POJ2367 Genealogical tree
POJ1094 Sorting It All Out