拓扑排序：（1）由偏序变成全序的过程！直观的说，偏序指集合中仅有部分成员之间可比较！而全序指集合中全体成员之间均可比较！

                    （2）将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

数据结构中进行拓扑排序的方法：

方法一：

（1）在有向图中选一个没有前驱的顶点且输出之！

（2）从图中删除该顶点和所有以它为尾的弧。

（3）重复上述两部，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中存在环！

代码：

#include <iostream>#include <string>using namespace std;const int MAXN = 1000;int G[MAXN][MAXN], n, m, count = 0;   //n代表DAG中的顶点的个数，m代表DAG中的边的个数！int ans[MAXN];bool topoSort(int a[][MAXN]) {	int into[MAXN];   //记录所有顶点的入度。	memset(into, 0, sizeof(into));	for(int i = 0; i < n; ++i) {		for(int j = 0; j < n; ++j) {			if(a[i][j])  ++into[j]; //求出图中所有顶点的入度！		}	}	for(int i = 0; i < n; ++i) {  //循环n次，每一次加入一个点到拓扑排序中去！		int j = 0;		while(into[j] != 0) {  //寻找图中入度为零的点！			++j;			if(j >= n) return false;  //DAG中存在有向环！		}		ans[i] = j;  //把该入度为零的点放入拓扑排序中！		into[j] = -1;   //该点放进拓扑排序以后，把他的入度标记为-1，为了下一次找入度为零的点做准备！		for(int k = 0; k < n; ++k) {    //没加入一个点到拓扑排序中以后，更新各顶点的入度！			if(a[j][k])  --into[k];		}	}	return true;}int main() {	cin >> n >> m;	memset(G, 0, sizeof(G));	for(int i = 0; i < m; ++i) {		int u, v;		cin >> u >> v;		G[u][v] = 1;	}	if(topoSort(G))	{		for(int i = 0; i < n; ++i) {			cout << ans[i] << " ";		}		cout << endl;	}else {		cout << "can not topoSort, because DAG has a circle" << endl;	}	return 0;}

方法二：

当有向图中无环的时候，可以利用dfs来进行拓扑排序。因为图中无环，则由图中某点出发进行DFS时，最先退出DFS函数的顶点即出度为零的点，是拓扑排序中最后一个顶点。所以按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。

下面的代码中：c[u]==0 代表该点u从来没有调用过dfs(u)，c[u]==1则代表递归调用过dfs(u)和u的所有子孙，c[u]==-1 代表该点u正在调用dfs(u)（即递归调用dfs(u)正在栈帧中，尚未返回）。

#include <iostream>#include <string>using namespace std;const int MAXN = 1000;int n, m, t;int G[MAXN][MAXN], c[MAXN];bool dfs(int u) {	c[u] = -1;   //开始递归调用u节点，所以设置c[u] = -1;	for(int v = 0; v < n; ++v) if(G[u][v]){		if(c[v] < 0) return false;      //如果u的一个子孙节点v正在调用中，说明该DAG存在有向环，则返回false		else if(!c[v] && !dfs(v)) return false   //如果u的一个子孙节点v从来没调用过，但是v的子树中存在有向环，则返回false	}	c[u] = 1;   //检查完了u节点的所有子孙，中途没有返回false，说明u的子树中不存在有向环	topo[--t] = u;  //所以把该节点加入到拓扑排序中	return true;}bool topoSort() {	t = n;	memset(c, 0, sizeof(c));	for(int u = 0; u < n; ++i)  if(!c[u]){    //如果该节点u从来没有递归调用过		if(!dfs(u)) return false;     //如果该节点u的所有子树中存在有向环，则返回false	}	return true;}int main() {	cin >> n >> m;	memset(G, 0, sizeof(G));	for(int i = 0; i < m; ++i) {		int u, v;		cin >> u >> v;		G[u][v] = 1;	}	if(topoSort()){		for(int i = 0; i < n; ++i){			cout << topo[i] << " ";		}		cout << endl;	}else{		cout << "can not topoSort, because DAG has a circle" << endl;	}	return 0;}