定义：
拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条边从Vi到Vj的路径，那么在排序中Vj就出现在Vi的后面。
具体实例：
在我们的大学课程中，常出现这么一种情况，比如在选修算法设计前必须先选修数据结构课程。如果，我们用图论来表示的话，（v, w）表示为课程v必须在课程w选修前选修完。
前提：
要满足可以使用拓扑排序的前提是：图中不含有圈。假设存在这样的两个关系（v,w）和（w,v），那么必定是不满足拓扑排序的定义的。
简单拓扑：
先找到任意一个没有入边的顶点，然后显示该顶点，并将它及其边一起从图中删除，然后，再对剩余的点做同样的处理。
伪代码：
//拓扑排序
void topsort() throws CycleFoundException{
for (int counter = 0; counter < NUM_VERTICES; counter ++){
//查找到入度为0的点
Vertex v = findNewVertexIndegreeZero();
if (v == null)
throw new CycleFoundException();
//记录该点的位置
v.topNum = counter;
//删除掉与v相连的边
for each Vertex w adjacent to v
w.indegree--;
}
}
改进的拓扑排序：
首先，对每个顶点计算它的入度，然后，将所有入度为0的顶点放入一个初始为空的队列中。当队列不为空时，删除一个顶点v，并将与v邻接的所有顶点的入度减1.只要一个顶点的入度降为0，就把该顶点放入队列中。
伪代码：
void topsort() throws CycleFoundException{
//用来记录入度为0的顶点
Queue<Vertex> q = new Queue<Vertext>();
int counter = 0;
//将入度为0的顶点加入到队列中
for each Vertex v
if (v.indegree == 0)
q.enqueue(v);
while( !q.isEmpty()){
//取出队列中的顶点
Vertex v = q.dequeue();
//记入该点位置
v.topNum = ++counter;
//将与改点相关的边都删除
for each Vertex w adjacent to v
//若删边后，该点入度为0，则加入队列中
if( --w.indegree == 0)
q.enqueue(w);
}
//若counter不等于顶点数，那么说明图中存在圈
if (counter != NUM_VERTICES)
throw new CycleFoundException();
}
应用一：判断图中是否存在圈
public boolean topSort(int numCounts, int[][] inputs){
//邻接矩阵
int[][] matrix = new int[numCounts][numCounts];
//记录顶点的入度
int[] indegree = new int[numCounts];
//初始化
for (int i = 0; i < inputs.length; i ++){
int front = inputs[i][0];
int behind = inputs[i][1];
//排除出现重复的情况，比如出现两次(1,2),(1,2)
if (matrix[front][behind] == 0)
indegree[behind] ++;
matrix[front][behind] = 1;
}
//记录个数，用来判断图是否存在圈
int count = 0;
//定义队列
Queue<Integer> queue = new LinkedList<>();
//将入度为0的顶点加入到队列中
for (int i = 0; i < indegree.length; i ++){
if (indegree[i] == 0)
queue.offer(i);
}
while (!queue.isEmpty()){
//获取到队列中队头
int current = queue.poll();
count ++;
//进行删边
for (int i = 0; i < numCounts; i ++){
if (matrix[current][i] != 0){
//若删边后，入度为0，则加入队列中
if (--indegree[i] == 0)
queue.offer(i);
}
}
}
return count == numCounts;
}
