定義：
拓撲排序是對有向無圈圖的頂點的一種排序煎饼，使得如果存在一條邊從Vi到Vj的路徑氓润，那么在排序中Vj就出現(xiàn)在Vi的后面。
具體實例：
在我們的大學課程中，常出現(xiàn)這么一種情況芋哭，比如在選修算法設(shè)計前必須先選修數(shù)據(jù)結(jié)構(gòu)課程。如果郁副，我們用圖論來表示的話减牺，（v, w）表示為課程v必須在課程w選修前選修完。
前提：
要滿足可以使用拓撲排序的前提是：圖中不含有圈存谎。假設(shè)存在這樣的兩個關(guān)系（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;
//將與改點相關(guān)的邊都刪除
for each Vertex w adjacent to v
//若刪邊后产禾，該點入度為0排作，則加入隊列中
if( --w.indegree == 0)
q.enqueue(w);
}
//若counter不等于頂點數(shù)，那么說明圖中存在圈
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];
//排除出現(xiàn)重復的情況亚情，比如出現(xiàn)兩次(1,2),(1,2)
if (matrix[front][behind] == 0)
indegree[behind] ++;
matrix[front][behind] = 1;
}
//記錄個數(shù)纽绍，用來判斷圖是否存在圈
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;
}
