學習總結---拓撲排序

拓撲排序

什麼是拓撲序列

通常，這樣的線性序列稱為滿足拓撲次序(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;
}      

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]);
  }
}      

下面推薦一些習題，還有鄙人的一些解題報告，話說剛開始寫的很渣，見諒：

比較簡單

uva 10305 

hdu 1285

hdu 3342

這題必須用到鄰接表

hdu 2647

難度加深

uva196

難度較大（考查到并查集+STL）

hdu 1811

（歡迎補充）