拓扑排序的定义是：将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。
适用范围：有向无环图（DAG），如果图中存在环路的话那么讨论就没有意义，当然在编程中需要对图是否有环进行判断。
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int MAX = 50;
// 邻接矩阵来存储点和边的信息
int G[MAX][MAX];
/* 节点是否有访问过，0 表示没有, 1 表示已经访问过,
-1 表示正在访问,即正在递归的调用帧中*/
int visit[MAX];
int n; /*n 表示节点的个数*/
stack<int> s;// 存放排序后的结果
void read()
{
printf("Please input the number of vertex:");
scanf("%d", &n);
printf("\nPlease input the information of edge. Input \"-1 -1\" indicate the end .\n");
printf("1 to n is number of vertex.\n");
int begin, end;
memset(G, 0, sizeof(G));
while(1)
{
scanf("%d %d", &begin, &end);
if(begin == -1) break;
G[begin][end] = 1;
}
}
bool dfs(int pos)
{
visit[pos] = -1;
for(int i=1; i <= n; i++)
{
if(G[pos][i])
{
if(visit[i] < 0)return false;
else if(!visit[i] && !dfs(i)) return false;
}
}
visit[pos] = 1;
s.push(pos);
return true;
}
bool topoSort()
{
memset(visit, 0, sizeof(visit));
for(int i=1; i <= n; i++)
{
if(!visit[i])
{
if(!dfs(i))// 如果存在环路则不能进行拓扑排序
return false;
}
}
return true;
}
int main()
{
freopen("in.txt","r",stdin);
read();
if(!topoSort())
printf("has cycle!\n");
else{
while(!s.empty())
{
printf("%d ", s.top());
s.pop();
}
}
return 0;
}设置一个visit 数组表示当前的节点是否被访问过，1表示访问过，0反之， -1的话就是正在被访问，因为在DFS 中用递归形式进行的，正在被访问表示当前正在递归帧中。
在递归中可以看到如果下一个点的visit 是-1 的话，那么就可以确定当前是环路，因为-1 是表示正在递归中的帧，而当遇到了点是-1 的话。就可以说明当前的点已经在此次递归中访问过了。即环路。
结果用栈的后进先出来保存，即在访问完一个节点之后，将这个节点加到当前拓扑序列的首部。之所以加到首部，是因为每次访问完之后，当前的点都是最后的节点。比如 1->2, 2->3; 因为我们在访问的时候都是从前访问到后的，那么最后访问的数就是最后的数。
接下来说的是环路的检测.
我们都知道如果一张图进行调整的话那么最后就可以形成一棵树，这也是图论中最小生成树的理论前提。因为树是没有环的，只有父与子的关系，我们在讨论图的环路问题上如果将图转换为一颗树，即认为此图是没有环路的。
如上图所示，在一颗树中如果找到了叶子节点，那么就可以顺着枝干找到根节点，然后把叶子节点都砍掉，那么此时的根节点就变成了叶子节点，循环往复，最后整棵树都会被砍掉。如图中所示，先找到最底层的红叶子节点，然后再往上找到蓝色叶子节点，最后一直到根节点。有点明白了吗？因为树是绝对不会有环的，那么我们就可以把图中的节点当成树的节点砍掉，最后如果还剩了节点，那么就可以得出结论有环，否则就没环。这有点像是kruskal 算法中对安全边的定义，如果在确认这条边是安全边（即是树的边的话），那么就加入到结果集中，同样的道理，如果我能确定一个节点的度是树中的一条边的话，那么我们也可以放心的把它砍掉。
最后我们总结下，
（1）.因为一个环的度总是大于等于2的，那么就把度等于1 的点都砍掉，接着把与这条边相邻的点的度减去1. 然后用一个队列把度等于1的点存起来，接着就回到 标号（1），如果最后还剩下点，那么就有环，否则无环。
一个点的度大于等于2，可以看成是一个树中的根节点，而度为1的点则可以认为是树中的最底层叶子节点。
图论：回路判断和拓扑排序（DFS）,布布扣,bubuko.com
原文：http://blog.csdn.net/china_zoujinyong/article/details/20143255
