拓?fù)渑判虻慕榻B和如何使用拓?fù)渑判蚪鉀Q一個(gè)問題

拓?fù)渑判蚴?a target="_blank">算法課經(jīng)典內(nèi)容之一，但是學(xué)的時(shí)候如果只是被動(dòng)接收，那就很容易淪為“算法背誦”，很快就記憶模糊了。這一次同樣的，我們從主動(dòng)發(fā)明的出發(fā)點(diǎn)去搞清楚這個(gè)問題的機(jī)理，就很難遺忘了。

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

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

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

1

動(dòng)機(jī)：前提關(guān)系

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

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

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

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

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

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

2

問題

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

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

3

徒手體會

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

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

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

4

初步解法

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

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

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

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

5

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

浪費(fèi)1

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

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

浪費(fèi)2

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

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

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

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

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

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

6

標(biāo)準(zhǔn)解法 BFS

這樣子迭代優(yōu)化出來的做法，其實(shí)就是拓?fù)渑判蛩^的BFS解法。我們用具體的例子直觀地描述一遍。

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

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

如此這般，循環(huán)下去，每次找到下一個(gè)可以做的任務(wù)，可以一路把拓?fù)渑判蜉敵龀鰜怼?/p>

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

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

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

7

標(biāo)準(zhǔn)解法 DFS：目標(biāo)導(dǎo)向

我很久以前首次接觸這個(gè)問題的時(shí)候，發(fā)明的就是上面BFS的解法，因?yàn)樗鲜挛镒匀煌七M(jìn)的順序，“撿當(dāng)前能做的東西做”。一直到大學(xué)的時(shí)候我才知道，原來有簡便得多的方法，雖然理論復(fù)雜度相同，但想起來、寫起來都要簡潔很多，這就是拓?fù)渑判虻乃^DFS解法。非常有意思的是，這個(gè)解法來自于“從目標(biāo)出發(fā)，一步步倒推”的結(jié)果導(dǎo)向型思路。

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

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

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

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

當(dāng)然，為了獲得全圖的拓?fù)渑判颍覀冞€需要一個(gè)粗暴的循環(huán)——

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

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

8

思考：環(huán)

以上我們就介紹完了兩種常見的拓?fù)渑判蛩惴ā?/p>

但是接觸過這個(gè)問題的人都知道，對于一個(gè)有向圖，首先拓?fù)渑判蚴欠翊嬖诙嫉么騻€(gè)問號。之前的討論中我刻意忽略了這個(gè)問題，因?yàn)閷τ诔鯇W(xué)者來說，同時(shí)操心太多頭緒可能會干擾思考?，F(xiàn)在，是時(shí)候把這個(gè)問題重新加入考慮，正好也作為對之前內(nèi)容的進(jìn)一步思維練習(xí)。

問題：拓?fù)渑判蚴裁磿r(shí)候根本就不存在呢？

當(dāng)然，舉出一個(gè)沒有拓?fù)渑判虻睦硬浑y——當(dāng)兩個(gè)任務(wù)直接或間接互為前提條件的時(shí)候，就沒法完成了，比如：

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

有環(huán)就沒法拓?fù)渑判?，這個(gè)比較好理解。反過來的方向，有向圖如果沒有環(huán)就一定有拓?fù)渑判颍枰晕?shù)學(xué)一點(diǎn)的證明，為了保持本文的flow，就跳過留給有興趣的人自己想了。

于是乎，我們有結(jié)論，拓?fù)渑判蛞欢ń⒃凇坝邢驘o環(huán)圖”之上。那么怎么在算法中檢查環(huán)的存在呢？也就是說，我們面對的問題變得更一般了一些，現(xiàn)在任務(wù)不是給定有向無環(huán)圖，找出一個(gè)拓?fù)渑判颍牵?/p>

給定一個(gè)有向圖，輸出拓?fù)渑判颍蛘吲卸▓D中有環(huán)。

BFS解法中加入判斷

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

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

。

。

。

。

。

。

。

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

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

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

DFS解法中加入判斷

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

完成小目標(biāo)(D)

→ 完成小目標(biāo)(A),

完成小目標(biāo)(G)

→ 完成小目標(biāo)(E)

→ 完成小目標(biāo)(D)

→ ...

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