什么是拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序，它使得如果存在一条从Vi到Vj的的路径，那么在排序中Vj出现在Vi的后面。

表示课程结构的无圈图

上图是表示某个大学的课程结构。有向边（v，w)表明课程v必须在课程w选修前修完。这些课程的拓扑排序不会破坏课程结构要求的任意课程序列。

但是，如果图含有圈，那么拓扑排序是不可能的，因为对于圈上的两个顶点v和w，v先于w同时w又先于v。另外，排序不必是唯一的；任何合理的排序都是可以的。

一个无圈图

上图中v1,v2,v5,v4,v3,v7,v6和v1,v2,v5,v4,v7,v3,v6两个都是拓扑排序。

算法

一个简单的求拓扑排序的算法是先找出任意一个没有入边（边方向都是向其他顶点的）的顶点。然后我们显示出该顶点，并将它和它的边一起从图中删除，然后，我们对图的其余部分应用同样的方法处理。

为了将上述方法形式化，我们定义顶点v的入度（indegree）定义为边（u，w)的条数。我们计算所有图中顶点的入度。假设Indegree数组被初始化且图被读入一个邻接表中，则此时我们可以应用如下为代码生成一个拓扑排序：

void Topsort(Graph G){  	int Counter; 		Vertex V, W;  	for(Counter = 0; Counter < NumVertex; ++Counter)    {      		V = FindNewVertextofIndegreeZero();      		/*扫描Indegree数组，寻找一个尚未被分配拓扑编号的入度为0的定点*/      		/*如果这样的顶点不存在，那么返回NotAVertex，这就意味着该图有圈*/      		if(V == NotAVertex)          {            	Error("Graph has a cycle");            	break;          }      		TopNum[V] = Counter; /*该数组存放拓扑编号*/      		for each W adjacent to V          		Indegree[W]--;    }}

我们可以通过将所有（为分配拓扑编号）入度为0的顶点放在一个特殊的盒子中，此时FindNewVertextofIndegreeZero()返回（并删除）盒子中的任一顶点。当我们降低这些邻接顶点的入度时，检查每一个顶点并在它的入度降为0时把它放入盒子中。

为了实现这个盒子，我们可以用一个栈或者队列。

首先，对每一个顶点计算它的入度。

然后，将所有入度为0的顶点放入一个初始为空的队列，并将与v邻接的所有的顶点的入度减1.只要一个顶点的入度降为0，就该把该顶点放入队列中。此时，拓扑排序就是顶点出队的顺序。下图显示对之前一个无圈图每一阶段之后的状态。

这个算法的伪代码如下，这里我们假设图已经被读到一个邻接表中且入度已计算并放入一个数组内。在实践中做这件工作的方便方法通常是把每一个顶点的入度放入头单元中。

void Topsort(Graph G){  		Queue Q;  		int Counter = 0;  		Q = CreateQueue(NumVertex);MakeEmpty(Q);  		for each vertex V      	if(Indegree[V] == 0)          Equeue(V, Q)  		while(!IsEmpty(Q))      {        	V = Dequeue(Q);        	TopNum[V] = ++Counter;        	         	for each W adjancent to V          	if(--Indegree[W] == 0)              Equeue(W, Q);      }  	  		if(Counter != Numbertex)        Error("Graph has a cycle");  		DisposeQueue(Q);}