打印一种拓扑排序(假定给的是有向无环图时）DFS+栈

一、定义：

在计算机科学领域，有向图的拓扑排序是其顶点的线性排序，使得对于从顶点u 到顶点v的每个有向边uv，u在排序中都在v之前。
例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。
如果且仅当图形没有定向循环，即如果它是有向无环图（DAG），则拓扑排序是可能的。
任何DAG具有至少一个拓扑排序，并且已知这些算法用于在线性时间内构建任何DAG的拓扑排序。
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）：
1、每个顶点出现且只出现一次；
2、若A在序列中排在B的前面，则在图中不存在从B到A的路径。

应用：

二、算法：

DFS+栈实现：只能求解那些已经确定是DAG(有向无环图)的一种拓扑排序

假如给定的图是一个有向无环图，那么通过DFS+栈就能找到一个拓扑排序。
因为DFS的时候总是出度为0的顶点那一层的DFS先完成(因为假定给的是有向无环图),然后在回溯到它的双亲（DFS树里的双亲)那一层，遍历完邻居后也完成然后回溯。所以每个(因为选择的顶点不一样，DFS树可能不一止一颗)DFS树中，子孙都是先于祖先完成的，这与拓扑排序正好相反，所以可以先用栈存各个元素，然后从栈顶依次打印，出栈就是一个拓扑排序了。
当有多颗DFS树时，先产生的DFS树的里各顶点的拓扑排序肯定要后于后产生的DFS树，因先产生的DFS里的顶点肯定没有有向边指向后产生的DFS树的顶点，但后产生的DFS树里却有可能有有向边指向先产生的DFS树的顶点。
代码：

#include<iostream>
#include<list>
#include<stack>

using namespace std;

class Graph
{
	int n; 		   //顶点数
	list<int> *adj;  //邻接表  
	void topologicalSortUtil(int u, bool visited[],stack<int>&stk); 
public:
	Graph(int _n) { n = _n; adj = new list<int>[_n];}
	~Graph(){ delete [] adj; }
	void addEdge(int v, int w){ adj[v].push_back(w); }
	void topologicalSort(); 	 
};
void Graph::topologicalSortUtil(int u, bool visited[], stack<int>&stk)
{
	visited[u] = true;
	
	list<int>::iterator it;
	for(it = adj[u].begin(); it != adj[u].end(); it++)
	{
		if(!visited[*it])
		{
			topologicalSortUtil(*it, visited, stk);
		}
	} 
	stk.push(u);
} 
void Graph::topologicalSort()
{
	bool *visited = new bool[n];
	for(int i = 0; i < n; i++)
	{
		visited[i] = false;
	}
	
	stack<int>stk;
	for(int i = 0; i < n; i++)
	{
		if(!visited[i])
		{
			topologicalSortUtil(i, visited, stk); 
		}
	}
	
	while(!stk.empty())			//打印 
	{
		cout<<stk.top()<<" ";
		stk.pop();
	}	
}
int main()
{
	Graph g(6); 
    g.addEdge(5, 2); 
    g.addEdge(5, 0); 
    g.addEdge(4, 0); 
    g.addEdge(4, 1); 
    g.addEdge(2, 3); 
    g.addEdge(3, 1);
    cout<<"这个图的拓扑排序为:"<<endl; 
    g.topologicalSort();
    return 0;
}