拓?fù)渑判蚴撬惴ㄕn經(jīng)典內(nèi)容之一戏售，但是學(xué)的時(shí)候如果只是被動接收，那就很容易淪為“算法背誦”贷帮，很快就記憶模糊了。這一次同樣的诱告，我們從主動發(fā)明的出發(fā)點(diǎn)去搞清楚這個(gè)問題的機(jī)理撵枢，就很難遺忘了。
跟上回一樣精居，從發(fā)明的角度锄禽，我們只要問兩點(diǎn)：
(1) 我們想解決一個(gè)什么問題？
(2) 這個(gè)問題如何最好地解決靴姿？
動機(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.已完成 → 打擾了乘碑， return
2.未完成 → 好的挖息，干它
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ù)渑判?strong>是否存在都得打個(gè)問號宛官。之前的討論中我刻意忽略了這個(gè)問題，因?yàn)閷τ诔鯇W(xué)者來說瓦糕，同時(shí)操心太多頭緒可能會干擾思考〉紫矗現(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)想象空間盛垦，由有興趣朋友自己思考品玩 :)
