那么這么一個(gè)圖的「拓?fù)湫颉故鞘裁匆馑寄?#xff1f;

我們借用百度百科[1]的這個(gè)課程表來說明。

這里有 9 門課程，有些課程是有先修課程的要求的，就是你要先學(xué)了「最右側(cè)這一欄要求的這個(gè)課」才能再去選「高階」的課程。

那么這個(gè)例子中拓?fù)渑判虻囊馑季褪?#xff1a;
就是求解一種可行的順序，能夠讓我把所有課都學(xué)了。

那怎么做呢？

首先我們可以用圖來描述它，圖的兩個(gè)要素是頂點(diǎn)和邊，那么在這里：

• 頂點(diǎn)：每門課

• 邊：起點(diǎn)的課程是終點(diǎn)的課程的先修課

畫出來長(zhǎng)這個(gè)樣：

這種圖叫 AOV (Activity On Vertex) 網(wǎng)絡(luò)，在這種圖里：

• 頂點(diǎn)：表示活動(dòng)；

• 邊：表示活動(dòng)間的先后關(guān)系

所以一個(gè) AOV 網(wǎng)應(yīng)該是一個(gè) DAG，即有向無(wú)環(huán)圖，否則某些活動(dòng)會(huì)無(wú)法進(jìn)行。
那么所有活動(dòng)可以排成一個(gè)可行線性序列，這個(gè)序列就是拓?fù)湫蛄小?/p>

那么這個(gè)序列的實(shí)際意義是：
按照這個(gè)順序，在每個(gè)項(xiàng)目開始時(shí)，能夠保證它的前驅(qū)活動(dòng)都已完成，從而使整個(gè)工程順利進(jìn)行。

回到我們這個(gè)例子中：

這樣，我們就把所有課程學(xué)完了，也就得到了這個(gè)圖的一個(gè)拓?fù)渑判颉?/p>

注意，有時(shí)候拓?fù)湫虿⒉皇俏ㄒ坏?#xff0c;比如在這個(gè)例子中，先學(xué) C1 再學(xué) C2，和先 C2 后 C1 都行，都是這個(gè)圖的正確的拓?fù)湫?#xff0c;但這是兩個(gè)順序了。

所以面試的時(shí)候要問下面試官，是要求解任意解，還是列出所有解。

我們總結(jié)一下，在這個(gè)圖里的邊表示的是一種依賴關(guān)系，如果要修下一門課，就要先把前一門課修了。

這和打游戲里一樣一樣的嘛，要拿到一個(gè)道具，就要先做 A 任務(wù)，再完成 B 任務(wù)，最終終于能到達(dá)目的地了。

# 算法詳解

在上面的圖里，大家很容易就看出來了它的拓?fù)湫?#xff0c;但當(dāng)工程越來越龐大時(shí)，依賴關(guān)系也會(huì)變得錯(cuò)綜復(fù)雜，那就需要用一種系統(tǒng)性的方式方法來求解了。

那么我們回想一下剛剛自己找拓?fù)湫虻倪^程，為什么我們先看上了 C1, C2?

因?yàn)樗鼈儧]有依賴別人啊，也就是它的入度為 0.

入度：頂點(diǎn)的入度是指「指向該頂點(diǎn)的邊」的數(shù)量；
出度：頂點(diǎn)的出度是指該頂點(diǎn)指向其他點(diǎn)的邊的數(shù)量。

所以我們先執(zhí)行入度為 0 的那些點(diǎn)，那也就是要記錄每個(gè)頂點(diǎn)的入度。

因?yàn)橹挥挟?dāng)它的 入度 = 0 的時(shí)候，我們才能執(zhí)行它。

在剛才的例子里，最開始 C1, C2 的入度就是 0，所以我們可以先執(zhí)行這兩個(gè)。

那在這個(gè)算法里第一步就是得到每個(gè)頂點(diǎn)的入度。

Step0: 預(yù)處理得到每個(gè)點(diǎn)的入度

我們可以用一個(gè) HashMap 來存放這個(gè)信息，或者用一個(gè)數(shù)組會(huì)更精巧。

在文中為了方便展示，我就用表格了：

Step1

拿到了這個(gè)之后，就可以執(zhí)行入度為 0 的這些點(diǎn)了，也就是 C1, C2.

那我們把可以被執(zhí)行的這些點(diǎn)，放入一個(gè)待執(zhí)行的容器里，這樣之后我們一個(gè)個(gè)的從這個(gè)容器里取頂點(diǎn)就好了。

至于這個(gè)容器究竟選哪種數(shù)據(jù)結(jié)構(gòu)，這取決于我們需要做哪些操作，再看哪種數(shù)據(jù)結(jié)構(gòu)可以為之服務(wù)。

那么首先可以把[C1, C2]放入容器中，然后想想我們需要哪些操作吧！

我們最常做的操作無(wú)非就是把點(diǎn)放進(jìn)來，把點(diǎn)拿出去執(zhí)行了，也就是需要一個(gè) offer 和 poll 操作比較高效的數(shù)據(jù)結(jié)構(gòu)，那么 queue 就夠用了。

（其他的也行，放進(jìn)來這個(gè)容器里的頂點(diǎn)的地位都是一樣的，都是可以執(zhí)行的，和進(jìn)來的順序無(wú)關(guān)，但何必非得給自己找麻煩呢？一個(gè)常規(guī)順序的簡(jiǎn)簡(jiǎn)單單的 queue 就夠用了。）

然后就需要把某些點(diǎn)拿出去執(zhí)行了。

【劃重點(diǎn)】當(dāng)我們把 C1 拿出來執(zhí)行，那這意味這什么？

答：意味著「以 C1 為頂點(diǎn)」的「指向其他點(diǎn)」的「邊」都消失了，也就是 C1 的出度變成了 0.

如下圖，也就是這兩條邊可以消失了。

那么此時(shí)我們就可以更新 C1 所指向的那些點(diǎn)也就是 C3 和 C8 的 入度 了，更新后的數(shù)組如下：

那我們這里看到很關(guān)鍵的一步，C8 的入度變成了 0！

也就意味著 C8 此時(shí)沒有了任何依賴，可以放到我們的 queue 里等待執(zhí)行了。

此時(shí)我們的 queue 里就是：[C2, C8].

Step2

下一個(gè)我們?cè)賵?zhí)行 C2，

那么 C2 所指向的 C3, C5 的 入度-1，更新表格：

也就是 C3 和 C5 都沒有了任何束縛，可以放進(jìn) queue 里執(zhí)行了。

queue 此時(shí)變成：[C8, C3, C5]

Step3

那么下一步我們執(zhí)行 C8，

相應(yīng)的 C8 所指的 C9 的入度-1.更新表格：

那么 C9 沒有了任何要求，可以放進(jìn) queue 里執(zhí)行了。

queue 此時(shí)變成：[C3, C5, C9]

Step4

接下來執(zhí)行 C3，

相應(yīng)的 C3 所指的 C4 的入度-1.更新表格：

但是 C4 的入度并沒有變成 0，所以這一步?jīng)]有任何點(diǎn)可以加入 queue.

queue 此時(shí)變成 [C5, C9]

Step5

再執(zhí)行 C5，

那么 C5 所指的 C4 和 C6 的入度- 1.更新表格：

這里 C4 的依賴全都消失啦，那么可以把 C4 放進(jìn) queue 里了：

queue = [C9, C4]

Step6

然后執(zhí)行 C9，

那么 C9 所指的 C7 的入度- 1.

這里 C7 的入度并不為 0，還不能加入 queue，此時(shí) queue = [C4]

Step7

接著執(zhí)行 C4，

所以 C4 所指向的 C6 和 C7 的入度-1，更新表格：

C6 和 C7 的入度都變成 0 啦！！把它們放入 queue，繼續(xù)執(zhí)行到直到 queue 為空即可。

# 總結(jié)

好了，那我們梳理一下這個(gè)算法：

數(shù)據(jù)結(jié)構(gòu)

這里我們的入度表格可以用 map 來存放

Map: <key = Vertex, value = 入度>

但實(shí)際代碼中，我們用一個(gè) int array 來存儲(chǔ)也就夠了，數(shù)組的 index 表示每個(gè)頂點(diǎn)，數(shù)組里的數(shù)值來表示每個(gè)頂點(diǎn)的入度，這樣比 Map 更精巧。

然后用了一個(gè)普通的 queue，用來存放可以被執(zhí)行的那些 node.

過程

我們把入度為 0 的那些頂點(diǎn)放入 queue 中，然后通過每次執(zhí)行 queue 中的頂點(diǎn)，就可以讓依賴這個(gè)被執(zhí)行的頂點(diǎn)的那些點(diǎn)的 入度-1，如果有頂點(diǎn)的入度變成了 0，就可以放入 queue 了，直到 queue 為空。

細(xì)節(jié)

這里有幾點(diǎn)實(shí)現(xiàn)上的細(xì)節(jié)：

當(dāng)我們 check 是否有新的頂點(diǎn)的 入度 == 0 時(shí)，沒必要過一遍整個(gè) map 或者數(shù)組，只需要 check 剛剛改動(dòng)過的就好了。

另一個(gè)是如果題目沒有給這個(gè)圖是 DAG 的條件的話，那么有可能是不存在可行解的，那怎么判斷呢？很簡(jiǎn)單的一個(gè)方法就是比較一下最后結(jié)果中的頂點(diǎn)的個(gè)數(shù)和圖中所有頂點(diǎn)的個(gè)數(shù)是否相等，或者加個(gè)計(jì)數(shù)器，如果不相等，說明就不存在有效解。所以這個(gè)算法也可以用來判斷一個(gè)圖是不是有向無(wú)環(huán)圖。

很多題目給的條件可能是給這個(gè)圖的 edge list，也是表示圖的一種常用的方式。那么給的這個(gè) list 就是表示圖中的邊。這里要注意審題哦，看清楚是誰(shuí) depends on 誰(shuí)。其實(shí)圖的題一般都不會(huì)直接給你這個(gè)圖，而是給一個(gè)場(chǎng)景，需要你把它變回一個(gè)圖。

時(shí)間復(fù)雜度

注意??：對(duì)于圖的時(shí)間復(fù)雜度分析一定是兩個(gè)參數(shù)，因?yàn)閳D的頂點(diǎn)數(shù)和邊的數(shù)量沒有固定的關(guān)系，然而面試的時(shí)候很多同學(xué)張口就是 O(n)...

對(duì)于有 v 個(gè)頂點(diǎn)和 e 條邊的圖來說，

第一步，預(yù)處理得到 map 或者 array，需要過一遍所有的邊才行，所以是 O(e)；

第二步，把 入度 == 0 的點(diǎn)入隊(duì)出隊(duì)的操作是 O(v)，如果是一個(gè) DAG，那所有的點(diǎn)都需要入隊(duì)出隊(duì)一次；

第三步，每次執(zhí)行一個(gè)頂點(diǎn)的時(shí)候，要把它指向的那條邊消除了，這個(gè)總共執(zhí)行 e 次；

總：O(v + e)

空間復(fù)雜度

用了一個(gè)數(shù)組來存所有點(diǎn)的 indegree，之后的 queue 也是最多把所有的點(diǎn)放進(jìn)去，所以是 O(v).

代碼

關(guān)于這課程排序的問題，Leetcode 上有兩道題，一道是 207，問你能否完成所有課程，也就是問拓?fù)渑判蚴欠翊嬖?#xff1b;另一道是 210 題，是讓你返回任意一個(gè)拓?fù)漤樞?#xff0c;如果不能完成，那就返回一個(gè)空 array。

這里我們以 210 這道題來寫，更完整也更常考一些。

這里給的 input 就是我們剛剛說到的 edge?list.?

Example 1.?

Input:?2,?[[1,0]]

Output:?[0,1]

Explanation:?這里一共2門課，1的先修課程是0.?所以正確的選課順序是[0,?1].

Input:?4,?[[1,0],[2,0],[3,1],[3,2]]

Output:?[0,1,2,3]?or?[0,2,1,3]

Explanation:?這里這個(gè)例子畫出來如下圖

?

Example 3.?

Input:?2,?[[1,0],[0,1]]

Output:?null

Explanation:?這課沒法上了

還是附上題目吧，just in case, if you want to see the details.

?

另外，拓?fù)渑判蜻€可以用 DFS - 深度優(yōu)先搜索 來實(shí)現(xiàn)

# 實(shí)際應(yīng)用

我們上文已經(jīng)提到了它的一個(gè) use case，就是選課系統(tǒng)，這也是最常考的題目。

而拓?fù)渑判蜃钪匾膽?yīng)用就是關(guān)鍵路徑問題，這個(gè)問題對(duì)應(yīng)的是 AOE (Activity on Edge) 網(wǎng)絡(luò)。

AOE 網(wǎng)絡(luò)：頂點(diǎn)表示事件，邊表示活動(dòng)，邊上的權(quán)重來表示活動(dòng)所需要的時(shí)間。
AOV 網(wǎng)絡(luò)：頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)之間的依賴關(guān)系。

在 AOE 網(wǎng)中，從起點(diǎn)到終點(diǎn)具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑，在關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。AOE 網(wǎng)絡(luò)一般用來分析一個(gè)大項(xiàng)目的工序，分析至少需要花多少時(shí)間完成，以及每個(gè)活動(dòng)能有多少機(jī)動(dòng)時(shí)間。

其實(shí)對(duì)于任何一個(gè)任務(wù)之間有依賴關(guān)系的圖，都是適用的。

比如 pom 依賴引入 jar 包時(shí)，大家有沒有想過它是怎么導(dǎo)進(jìn)來一些你并沒有直接引入的 jar 包的？比如你并沒有引入 aop 的 jar 包，但它自動(dòng)出現(xiàn)了，這就是因?yàn)槟銓?dǎo)入的一些包是依賴于 aop 這個(gè) jar 包的，那么 maven 就自動(dòng)幫你導(dǎo)入了。

其他的實(shí)際應(yīng)用，知乎上專門有個(gè)帖子，在這里我總結(jié)一下：

如有其他補(bǔ)充，歡迎大家在評(píng)論區(qū)不吝賜教。

以上就是本文的全部?jī)?nèi)容了，拓?fù)渑判蚴欠浅Ｖ匾彩欠浅劭嫉囊活愃惴?#xff0c;面試大廠前一定要熟練掌握。

如果覺得寫的不錯(cuò)，請(qǐng)記得轉(zhuǎn)發(fā)評(píng)論，這是對(duì)我最大的認(rèn)可和鼓勵(lì)

總結(jié)

以上是生活随笔為你收集整理的带你深入了解拓扑排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。