0. 概述

學習下拓撲排序

1. 零入度算法

1. 1 拓撲排序

首先理解下拓撲排序

其實老師經(jīng)常干這事，如編講義，將已經(jīng)知道的知識點串起來變成講課序列。那怎么串起來呢？將知識點列出，將它們之間的相互關系描述下。要講priority queue那上一講需要講什么內容，要講hashing需要講哪些內容，需要羅列出來。但是講課不可能像分支一樣平行一分為二裂開，最終都會變成下面這樣平坦的線性序列。

（續(xù)）一個好的安排是什么呢？每當講到一個知識點時，它所依賴的知識點都應該在此前依然講過，這樣就會變成一個線性序列。將原來圖中所有的點整理成這樣一個線性次序，前面點與后面點的邊次序都是前指向后，沒有后指向前，這就是對原圖的拓撲排序。

1. 2 算法

• 如果真有這么一個圖，怎么排呢？
  
  因為這個圖有依賴關系，所以是不折不扣的有向圖，但有意思的是這里不能有環(huán)，如果有環(huán)路就有問題。

首先需要找到零入度的點——無任何依賴，在dag圖中必然有這么一個點，由于DAG子圖亦為DAG，于是可以利用減而治之思想，將這個零入度的點抹掉，接著找下一個零入度點。

• 那么這個算法如何實現(xiàn)？

圖中已經(jīng)有零入度的點A或B，任取一個，這里取A，放入隊列中，等價將A點及其邊從圖中刪除。由于DAG的子圖亦是DAG，所以還會有零入度的點，將B點放入隊列中，然后依次類推，當所有的點都放入隊列后，隊列中的節(jié)點順序就是拓撲排序。

但這個方法并不好，實現(xiàn)起來比較麻煩，需要每次去找那個零入度的點，而且刪除點及其邊的時候還要更新相應信息，可能會對圖產(chǎn)生傷害，那怎么做呢？看下下面的零出度算法

2. 零出度算法

2.1 算法

說服下自己，DAG既有零入度點也有零出度點，這個很重要，為什么這么講，因為之前的DFS（深度優(yōu)先搜索）可以幫我們實現(xiàn)這個方法。

這樣要做的事就比較簡單，不需要零入度算法那這樣改改度數(shù)等等。之前已經(jīng)造出DFS算法，這樣就可以搭DFS便車實現(xiàn)零出度算法。

如何實現(xiàn)呢？

2.2 實現(xiàn)

這里引入一個棧，排序結果將以逆序打印出來。隨便找一個點，這里首先訪問頂點V，將頂點V狀態(tài)初始值設置為DISCOVERED，接著枚舉V的所有鄰居，視u的狀態(tài)，分別處理，后續(xù)會做分析。訪問所有鄰居后，將頂點V的狀態(tài)設置為VISITED，然后頂點V入棧。

接著還有頂點V的鄰居處理方法還未做交代，怎么處理呢？

1. 若頂點U的狀態(tài)為UNDISCOVERED，更新頂點U的父親為V，邊的狀態(tài)為TREE，作遞歸調用，從頂點u處深入。
2. 頂點U的狀態(tài)為DISCOVERED，一旦發(fā)現(xiàn)后向邊，即圖非DAG圖，無拓撲排序，則退出而不再深入。
3. 頂點U的狀態(tài)為VISITED，更新下頂點狀態(tài)。

2.3. 復雜度

這里僅額外引入的棧，規(guī)模不超過頂點總數(shù)O(n)?？傮w而言，空間復雜度與基本的深度優(yōu)先搜索算法同樣，仍為O(n + e)。該算法的遞歸跟蹤過程與標準DFS搜索完全一致，且各遞歸實例自身的執(zhí)行時間依然保持為O(1)，故總體運行時間仍為O(n + e)。