拓撲排序是算法課經(jīng)典內(nèi)容之一，但是學的時候如果只是被動接收，那就很容易淪為“算法背誦”，很快就記憶模糊了。這一次同樣的，我們從主動發(fā)明的出發(fā)點去搞清楚這個問題的機理，就很難遺忘了。

跟上回一樣，從發(fā)明的角度，我們只要問兩點：

(1) 我們想解決一個什么問題？

(2) 這個問題如何最好地解決？

1

動機：前提關(guān)系

本文中我們想解決的各種問題，都有一個明確的共同范式：任務(wù)，和任務(wù)之間的先后順序，或者說前提關(guān)系。有很多任務(wù)需要完成，其中有的任務(wù)開始之前，會要求某些前提任務(wù)首先被完成。

這樣的具體例子很常見，生活中比如

先修課程：一系列課程，基礎(chǔ)課可以隨便修，想上稍微高級一點的課程可能會要求先修完若干門基礎(chǔ)一點的課程。在這樣“先修課程”的關(guān)系之下，怎么把一系列課全修完，就需要在順序上有一些計劃

計算機內(nèi)部這樣的情形更常見，比如：

軟件包批量安裝：安裝很多軟件包的時候，有的包會用到別的包，被用到就要先裝，安裝器就需要根據(jù)這些前提關(guān)系規(guī)劃安裝順序

計算任務(wù)：設(shè)置復雜的計算任務(wù)的時候，有的計算需要用到別的計算的結(jié)果，計算框架的scheduler就需要理清這里面隱含的先后關(guān)系，才能所有結(jié)果全算出來

2

問題

所以，對這個問題合理的抽象就是，有任務(wù)，也有任務(wù)之間的依賴關(guān)系，它們之間自然會形成一個dependency graph:

而我們想找出一種合理的任務(wù)順序，按這個順序依次完成任務(wù)，可以保證做到每件任務(wù)的時候，它的前提任務(wù)都已經(jīng)被完成。上圖中，比如 A-B-E-G-D-C-F。

3

徒手體會

先徒手操作一下，對這個問題產(chǎn)生一些最直觀認識。其實對于人來說，這個問題沒什么難度，大可以邊做邊想。比如當你面對一堆課程的時候（例子來源于本人將在程序員末日2038年胡亂編纂的“從入門到放棄”系列精品課程）

首先總該有一些課是直接可以上的，比如圖中“語言入門”和“數(shù)學基礎(chǔ)”。你完全可以選一門上就好了，比如你選“數(shù)學基礎(chǔ)”，上完之后這門就可以拋到腦后

順便這也有可能為新的課打開了大門，比如現(xiàn)在就新可以上“數(shù)據(jù)結(jié)構(gòu)和算法”了。所以直覺來看拓撲排序并沒有什么難度，只要有耐心，誰都可以一步步順著當前可以上的課上，成功地從入門到放棄（誤）。

4

初步解法

那么其實我們就已經(jīng)可以有一個最原始的解法了，非常簡單粗暴，但是至少可以給出正確的答案：每次重新審視這個圖，一個一個檢查還沒完成的任務(wù)，如果哪一個任務(wù)的所有前提都已完成，下一個就做它，也就是，加入輸出序列，并把這個新任務(wù)標記為完成。舉例說明，比如說當你做到某一步時，來到了下圖所示的這個情境中（灰色為已完成任務(wù)， 丑藍為待完成任務(wù)）

你可以一個個檢查有待完成的藍色任務(wù)們。C，它還有前提任務(wù)D沒有完成；D在等G；F也不行；G，誒，它的前提任務(wù)都已完成，好，那就它了。下一個輸出G，并且把它標為已完成。

如此往復，最終總能把所有任務(wù)都有條不紊地完成。

作為最原始的解法，它的效率不高。但是這并沒有關(guān)系，找到其中的浪費，一個個解決，自然就可以迭代出一個好的解法。

5

優(yōu)化：去掉浪費

浪費1

首先，“檢查前提任務(wù)有沒有都完成”這個步驟，可以簡潔一點。每個結(jié)點可以一直記著自己還有幾個前提任務(wù)沒有完成（結(jié)點的入度）。比如下圖，藍色數(shù)字標注還剩幾個前提任務(wù)

接下來，如果我們完成了A，可以去通知它的后繼結(jié)點們 B 和 D，告訴它們?nèi)攵瓤梢詼p1了。這樣，你只要看一個任務(wù)的未完成前提數(shù)有沒有降到0，就知道這個任務(wù)是不是可做。

浪費2

我們的流程還有一個巨大的浪費：我們在重復尋找已ready（入度為0）的結(jié)點。接著 ↑上圖↑ 的情形，我們發(fā)現(xiàn)A和G已經(jīng)入度為0，處于ready狀態(tài)；假設(shè)我們接下來選擇做A，于是 B 和 D 入度減1：

然后下一輪的時候，我們還需要遍歷所有藍色結(jié)點，去尋找那些ready的嗎？不需要：

我們上一輪就知道G的入度為0的，現(xiàn)在肯定沒變過

只有 A 的后繼 B 和 D 的入度發(fā)生了下降，其他的 C 和 F 這些結(jié)點完全沒受影響，那它們的入度既然之前不是0，現(xiàn)在沒變，肯定依然不是0

所以說，我們記著之前發(fā)現(xiàn)過的所有ready的結(jié)點，然后每次只需要在那些入度被更新的結(jié)點中尋找新的ready結(jié)點就夠了。如此一來，我們?nèi)サ袅舜罅康睦速M，也得出了一個算法了——

維護一個所有ready結(jié)點組成的集合，每次從里面選一個結(jié)點完成，把它的后繼的入度都減一，并在被更新的結(jié)點中找出新的ready結(jié)點，加入我們的集合。

6

標準解法 BFS

這樣子迭代優(yōu)化出來的做法，其實就是拓撲排序所謂的BFS解法。我們用具體的例子直觀地描述一遍。

初始化的時候，計算每個結(jié)點的入度，所有初始入度就為0的結(jié)點，都是處于ready狀態(tài)的任務(wù)，加入我們的集合（圖中標為丑綠）

接下來每一次，從綠色ready集里面隨便拿一個結(jié)點出來，比如 A，這個任務(wù)已經(jīng)處于ready狀態(tài)，所以完成它（輸出）；A任務(wù)完成以后，它的后繼結(jié)點 B 和 D 的入度都可以去掉 1，如果有哪個后繼結(jié)點在這個過程中入度降成了0 （比如B），那它也進入了ready狀態(tài)，我們就順手把它加入我們的ready集合。

如此這般，循環(huán)下去，每次找到下一個可以做的任務(wù)，可以一路把拓撲排序輸出出來。

圖看完了，再用迷幻的偽代碼描述一下：

初始化1：每個結(jié)點把自己的入度數(shù)好[乖巧]初始化2：建立一個ready集合，記錄下哪些結(jié)點已經(jīng)ready.把一開始入度就為0的源點都加入集合接下來只要集合里還有結(jié)點： 1. 從集合里隨便拿一個結(jié)點v出來 2. 把v輸出，并且通知它的所有后繼：你們的前提任務(wù)又少了一個，快把入度-1 3. 在順序通知的同時，如果哪個后繼發(fā)現(xiàn)自己的前提任務(wù)因此全部達成（入度降到0），就把自己加入ready大家庭如此往復，就獲得了這個圖的一個拓撲排序。

這樣一來，這個循環(huán)中，每條邊都正好被用到一次（為什么？），浪費已經(jīng)降到最小，我們知道已經(jīng)達到效率最優(yōu)解了。

7

標準解法 DFS：目標導向

我很久以前首次接觸這個問題的時候，發(fā)明的就是上面BFS的解法，因為它符合事物自然推進的順序，“撿當前能做的東西做”。一直到大學的時候我才知道，原來有簡便得多的方法，雖然理論復雜度相同，但想起來、寫起來都要簡潔很多，這就是拓撲排序的所謂DFS解法。非常有意思的是，這個解法來自于“從目標出發(fā)，一步步倒推”的結(jié)果導向型思路。

怎么說呢，就是面對一個dependency graph，我不是循序漸進撿ready的任務(wù)做，而是隨手指一個結(jié)點，比如下圖中的 “一個億”

然后先將其確立一個小目標，別的什么都不想，只求完成我指定的這個任務(wù)。確立“一個億”小目標之后，就要開始倒推了，為了能完成任務(wù)“一個億”，我得先完成它的所有前提，就是“悔創(chuàng)阿里”和“不知妻美”，于是乎對于每一個前提任務(wù)，你也可以同樣倒推（比如為了達成成就“不知妻美”，首先要做任務(wù)“普通人家”），依次去滿足他們的前提條件，一直到倒推到?jīng)]有前提的任務(wù)，或者之前已經(jīng)完成的任務(wù)為止。

這個自我重復的流程非常適合遞歸。直接上迷幻的偽代碼，大家感受一下它簡潔的魅力

（所有結(jié)點上都應(yīng)該有個標記，標該結(jié)點是否已完成/輸出過）function完成小目標(v)：先看看v之前有沒有被完成過1.已完成→打擾了，return2.未完成→好的，干它a)對于v的所有前提任務(wù)ui:遞歸調(diào)用完成小目標(ui)b)都完成之后，現(xiàn)在所有前提應(yīng)該都已滿足，就輸出v，并標記為已完成

當然，為了獲得全圖的拓撲排序，我們還需要一個粗暴的循環(huán)——

對于圖中所有結(jié)點v:調(diào)用完成小目標(v)

建議初次接觸的朋友自己試幾個結(jié)點感受一下，遞歸函數(shù)所倚靠的系統(tǒng)棧，如何就幫你把這個順序問題全部解決了。

8

思考：環(huán)

以上我們就介紹完了兩種常見的拓撲排序算法。

但是接觸過這個問題的人都知道，對于一個有向圖，首先拓撲排序是否存在都得打個問號。之前的討論中我刻意忽略了這個問題，因為對于初學者來說，同時操心太多頭緒可能會干擾思考?，F(xiàn)在，是時候把這個問題重新加入考慮，正好也作為對之前內(nèi)容的進一步思維練習。

問題：拓撲排序什么時候根本就不存在呢？

當然，舉出一個沒有拓撲排序的例子不難——當兩個任務(wù)直接或間接互為前提條件的時候，就沒法完成了，比如：

這些時候，圖中都有一個“環(huán)”的存在，循環(huán)調(diào)用，互為前提。

有環(huán)就沒法拓撲排序，這個比較好理解。反過來的方向，有向圖如果沒有環(huán)就一定有拓撲排序，需要稍微數(shù)學一點的證明，為了保持本文的flow，就跳過留給有興趣的人自己想了。

于是乎，我們有結(jié)論，拓撲排序一定建立在“有向無環(huán)圖”之上。那么怎么在算法中檢查環(huán)的存在呢？也就是說，我們面對的問題變得更一般了一些，現(xiàn)在任務(wù)不是給定有向無環(huán)圖，找出一個拓撲排序，而是：

給定一個有向圖，輸出拓撲排序，或者判定圖中有環(huán)。

BFS解法中加入判斷

回顧一下剛才的BFS解法，我們是用一個集合/容器記著所有目前已經(jīng)ready的結(jié)點，每次取出一個，輸出，然后在它的后繼中尋找新的ready結(jié)點加入集合。那么想象在一個有環(huán)的圖中會出現(xiàn)什么呢？

沒想明白的盆友可以先自己演繹一下。

。

。

。

。

。

。

。

如果在我們之前的圖中，將DE之間的邊反向，則會出現(xiàn)圖中紅色標注的環(huán)。

按照之前的方法運行我們的BFS算法，可以成功完成A，然后B，之后會卡在圖中所示的尷尬境地：沒有入度為0的結(jié)點了，所有未完成任務(wù)都要求別的任務(wù)先完成，誰也不讓誰，于是我們卡在這里再也進行不下去。

所以這就是BFS中我們判斷環(huán)的標準：如果算法進行到某一步，還有未完成任務(wù)，但ready集合為空，即沒有任務(wù)是ready的，則一定是有環(huán)把我們卡住了。

DFS解法中加入判斷

如果DFS解法遇到了有環(huán)的情況，會發(fā)生什么？如果還是用上圖的紅色環(huán)為例，為了完成D，你會調(diào)用如下序列

完成小目標(D)

→ 完成小目標(A),

完成小目標(G)

→ 完成小目標(E)

→ 完成小目標(D)

→ ...

你會發(fā)現(xiàn)這個遞歸進入一個死循環(huán)。所以判斷圖中有沒有環(huán)的方法，就是想辦法去發(fā)現(xiàn)自己的遞歸流程有沒有重復訪問同一個結(jié)點。但這其中有一些細節(jié)需要思考，比如其實訪問一個已訪問過的結(jié)點很多時候也是正常的——結(jié)點被訪問過可能是因為被之前某個任務(wù)完成了。所以可能需要我們想辦法區(qū)分這兩種情形。這是一個很有意思的問題，自己想明白會很有趣，所以我們照例在最后留一點想象空間，由有興趣朋友自己思考品玩 :)