拓撲排序什麼是拓撲序列
通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。離散數學中關於偏序和全序的定義：
若集合X上的關系是R,且R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關系。
設R是集合X上的偏序（Partial Order）,如果對每個x,y屬於X必有xRy 或 yRx，則稱R是集合X上的全序關系。
比較簡單的理解：偏序是指集合中只有部分成員可以比較，全序是指集合中所有的成員之間均可以比較。
注意：
①若將圖中頂點按拓撲次序排成一行，則圖中所有的有向邊均是從左指向右的。
②若圖中存在有向環，則不可能使頂點滿足拓撲次序。
③一個DAG的拓撲序列通常表示某種方案切實可行。
昨天花了一天的時間研究了下拓撲排序，覺得學到很多，所以寫一下總結。
<1>有向圖的表示方式可以分成鄰接矩陣和鄰接表兩種。
鄰接矩陣是指用一個n*n的數組，下標為i,j的位置記錄點i和點j的關系。（適用與稀疏矩陣，對內存空間要求要比較高）
鄰接表是單純記錄關系的數組，比如 i和 j 有關系， 就將 j 放在 [i][k]的位置（k為當前與i有關系的點數），這種表示法適用於關系較少的時候，但是引用進STL中的vector以後，好像數據量的大小對其就沒有什麼太大的影響了。
<2>拓撲排序：每次找到入度為0 的點，並將其出度清空（可以用DFS或BFS），跟據表示的方法不同，操作也會有所差別。
<3>給出有向圖之後，會有存在拓撲排序和不存在拓撲排序之分，如果圖中存在有向環，則不存在拓撲排序（就是在遍歷的過程中直接和間接的相互指向），在處理上只要記錄每個點的訪問狀態就可以了，是正在訪問（不滿足的情況），還是未訪問，或是已經訪問過（DFS)。
如果存在了拓撲排序，也會有拓撲排序唯不唯一的問題（如果沒有要求考慮這點，用DFS會號做一些），這點其實也好處理，只要每次入度為0的點只有一個才可以（BFS）。
DFS + 鄰接表
DFS + 鄰接矩陣。
int vis[MAXN];
int topo[MAXN], cnt;
bool DFS(int u){
vis[u] = -1; //表示當前正在訪問，如果再次訪問說明不存在topo排序。
for (int i = 0; i < n; i++){
if (G[u][i]){
if (vis[i] < 0)
return false; //存在有向環，失敗退出。
else if (!vis[i] && !DFS(i))
return false;
}
}
vis[u] = 1;
topo[--cnt] = u;
return true; // 成功記錄，返回true 。
}
bool toposort(){
cnt = n;
memset(vis, 0, sizeof(vis)); // 如果要考慮排序是否唯一，這邊每次都需將所有點遍歷過一遍，且每次只可有一點的入度為0。
for (int u = 0; u < n; u++)
if (!DFS(u))
return false;
return true;
}
// DFS + 鄰接矩陣。
int vis[MAXN];
int topo[MAXN], cnt;
bool DFS(int u){
vis[u] = -1; //表示當前正在訪問，如果再次訪問說明不存在topo排序。
for (int i = 0; i < n; i++){
if (G[u][i]){
if (vis[i] < 0)
return false; //存在有向環，失敗退出。
else if (!vis[i] && !DFS(i))
return false;
}
}
vis[u] = 1;
topo[--cnt] = u;
return true; // 成功記錄，返回true 。
}
bool toposort(){
cnt = n;
memset(vis, 0, sizeof(vis)); // 如果要考慮排序是否唯一，這邊每次都需將所有點遍歷過一遍，且每次只可有一點的入度為0。
for (int u = 0; u < n; u++)
if (!DFS(u))
return false;
return true;
}BFS(借助STL-queue) + 鄰接表（借助STL-vector)
// BFS + 鄰接表。
vector<int> G[MAXN]; // 鄰接表。
int son[MAXN]; // 入度數。
void topo(){
queue<int> que;
int ok = 0;
for (int i = 0; i < n; i++)
if (!son[i])
que.push(i); // 入度為0時入隊。
while (!que.empty()){
if (que.size() > 1)
ok = 1; // 當隊列中個數超多1時，表示有不唯一解。
int t = que.front();
que.pop();
cnt--; // 如果隊列為空後，計數器> 0， 說明存在環結構。
for (int i = 0; i < G[t].size(); i++)
if (--son[G[t][i]] == 0) // 判斷減掉當前點的關系後，點的入度是否為0。
que.push(G[t][i]);
}
}
