拓扑排序，对有向无圈图的顶点的一种排序，如果图中存在一条从顶点vi到vj的路径，那么在排序中vj必须出现vi后面，并且顶点都只出现一次。
度是指一个顶点所有与之相关联的边的数量。 入度是指以该顶点为终点的边的数量。 出度是指以该顶点为起点的边的数量。
在一个有向无圈图中，列出所有顶点的入度，找出一个入度为0的顶点，编号为1，然后删除图中所有以1号为起点的边。然后再找出一个入度为0的顶点，编号为2，重复上述步骤至图中没有顶点。 这个过程中有时会出现多个入度为0的顶点，这时算法可以继续下去，拓扑排序只要不违反上面两条原则就可以执行。 算法执行完毕，但是图中还有顶点没有输出，但是再也找不到入度为0的顶点了，这说明图中有环。（这不就是证明图中存在环么。。。）
实现是这样的，将所有还没有分配拓扑编号的入度为0的顶点放在队列中，在随后的执行过程中，队列不空，就推出队列的顶点，并编号它，然后将所有与它邻接的顶点的入度减1，只要某个顶点的入度减为0，就把他加入队列中。当最后实际编号的顶点数小于图的顶点数，就报告这个图有环。
void TopSort(Graph G,int TopNum[],int indegree[]) //图，拓扑排序结果，入度。 { Queue Q; int count=0; //编号计数 Vertex v,w; //顶点下标 AdjVNode M; //顶点
Q=MakeQueue(G->Nv); MakeEmpty(Q); for(i=0;i<G->Nv;i++) { if (indegree[i]==0) { Enqueue(i,Q); } } while(!IsEmpty(Q)) { v=Dequeue(Q); TopNum[v]=++count; //分配编号 for(M=G->G[v].FirstEdge->Next;;M=M->Next) //G-G[]是邻接表。 { indegree[M->Adjv]--; //M->Adjv是这个邻接点的下标 if (indegree[M->Adjv]==0) { Enqueue(M->Adjv,Q); //入度减为0的顶点进入队列 } } } if（count!=G->Nv) { printf("Graph has a cycle"); } DisposeQueue(Q); //删掉队列.}
