前言
大家好侥锦，這里是《齊姐聊算法》系列之拓?fù)渑判騿栴}视搏。
Topological sort 又稱 Topological order伟墙，這個(gè)名字有點(diǎn)迷惑性钳吟，因?yàn)橥負(fù)渑判虿⒉皇且粋€(gè)純粹的排序算法解幽，它只是針對(duì)某一類圖贴见，找到一個(gè)可以執(zhí)行的線性順序。
這個(gè)算法聽起來高大上躲株，如今的面試也很愛考片部，比如當(dāng)時(shí)我在面我司時(shí)有整整一輪是基于拓?fù)渑判虻脑O(shè)計(jì)。
但它其實(shí)是一個(gè)很好理解的算法霜定，跟著我的思路档悠，讓你再也不會(huì)忘記她。
有向無環(huán)圖
剛剛我們提到望浩，拓?fù)渑判蛑皇轻槍?duì)特定的一類圖辖所，那么是針對(duì)哪類圖的呢？
答：Directed acyclic graph (DAG)磨德，有向無環(huán)圖缘回。即：
- 這個(gè)圖的邊必須是有方向的；
- 圖內(nèi)無環(huán)典挑。
那么什么是方向呢酥宴？
比如微信好友就是有向的，你加了他好友他可能把你刪了你卻不知道您觉。幅虑。。那這個(gè)朋友關(guān)系就是單向的顾犹。倒庵。
什么是環(huán)？環(huán)是和方向有關(guān)的炫刷，從一個(gè)點(diǎn)出發(fā)能回到自己擎宝，這是環(huán)。
所以下圖左邊不是環(huán)浑玛，右邊是绍申。
那么如果一個(gè)圖里有環(huán)，比如右圖，想執(zhí)行 1 就要先執(zhí)行 3极阅，想執(zhí)行 3 就要先執(zhí)行 2胃碾，想執(zhí)行 2 就要先執(zhí)行 1，這成了個(gè)死循環(huán)筋搏，無法找到正確的打開方式仆百，所以找不到它的一個(gè)拓?fù)湫颉?/p>
總結(jié)：
- 如果這個(gè)圖不是 DAG，那么它是沒有拓?fù)湫虻模?/li>
- 如果是 DAG奔脐，那么它至少有一個(gè)拓?fù)湫颍?/li>
- 反之俄周，如果它存在一個(gè)拓?fù)湫颍敲催@個(gè)圖必定是 DGA.
所以這是一個(gè)充分必要條件髓迎。
拓?fù)渑判?/h2>
那么這么一個(gè)圖的「拓?fù)湫颉?/code>是什么意思呢峦朗？
我們借用百度百科的這個(gè)課程表來說明。
| 課程代號(hào) | 課程名稱 | 先修課程 |
|---|---|---|
| C1 | 高等數(shù)學(xué) | 無 |
| C2 | 程序設(shè)計(jì)基礎(chǔ) | 無 |
| C3 | 離散數(shù)學(xué) | C1, C2 |
| C4 | 數(shù)據(jù)結(jié)構(gòu) | C3, C5 |
| C5 | 算法語言 | C2 |
| C6 | 編譯技術(shù) | C4, C5 |
| C7 | 操作系統(tǒng) | C4, C9 |
| C8 | 普通物理 | C1 |
| C9 | 計(jì)算機(jī)原理 | C8 |
這里有 9 門課程排龄，有些課程是有先修課程的要求的波势，就是你要先學(xué)了「最右側(cè)這一欄要求的這個(gè)課」才能再去選「高階」的課程。
那么這個(gè)例子中拓?fù)渑判虻囊馑季褪牵?br> 就是求解一種可行的順序橄维，能夠讓我把所有課都學(xué)了尺铣。
那怎么做呢？
首先我們可以用圖來描述它挣郭，
圖的兩個(gè)要素是頂點(diǎn)和邊，
那么在這里：
- 頂點(diǎn)：每門課
- 邊：起點(diǎn)的課程是終點(diǎn)的課程的先修課
畫出來長這個(gè)樣：
這種圖叫 AOV (Activity On Vertex) 網(wǎng)絡(luò)疗韵，在這種圖里：
- 頂點(diǎn)：表示活動(dòng)兑障；
- 邊：表示活動(dòng)間的先后關(guān)系
所以一個(gè) AOV 網(wǎng)應(yīng)該是一個(gè) DAG，即有向無環(huán)圖蕉汪，否則某些活動(dòng)會(huì)無法進(jìn)行流译。
<span style="display:block;color:orangered;">那么所有活動(dòng)可以排成一個(gè)可行線性序列，這個(gè)序列就是拓?fù)湫蛄?/code>者疤。
那么這個(gè)序列的實(shí)際意義是：
按照這個(gè)順序福澡，在每個(gè)項(xiàng)目開始時(shí)，能夠保證它的前驅(qū)活動(dòng)都已完成驹马，從而使整個(gè)工程順利進(jìn)行革砸。
回到我們這個(gè)例子中：
我們一眼可以看出來要先學(xué) C1, C2，因?yàn)檫@兩門課沒有任何要求嘛糯累，大一的時(shí)候就學(xué)唄算利；
大二就可以學(xué)第二行的 C3, C5, C8 了，因?yàn)檫@三門課的先修課程就是 C1, C2泳姐，我們都學(xué)完了效拭；
大三可以學(xué)第三行的 C4, C9；
最后一年選剩下的 C6, C7。
這樣缎患，我們就把所有課程學(xué)完了慕的，也就得到了這個(gè)圖的一個(gè)拓?fù)渑判?/code>。
注意挤渔，有時(shí)候拓?fù)湫虿⒉皇俏ㄒ坏陌菇郑热缭谶@個(gè)例子中，先學(xué) C1 再學(xué) C2蚂蕴，和先 C2 后 C1 都行低散，都是這個(gè)圖的正確的拓?fù)湫颍@是兩個(gè)順序了骡楼。
所以面試的時(shí)候要問下面試官熔号，是要求解任意解，還是列出所有解鸟整。
我們總結(jié)一下引镊，
在這個(gè)圖里的邊表示的是一種依賴關(guān)系，如果要修下一門課篮条，就要先把前一門課修了弟头。
這和打游戲里一樣一樣的嘛，要拿到一個(gè)道具涉茧，就要先做 A 任務(wù)赴恨，再完成 B 任務(wù)，最終終于能到達(dá)目的地了伴栓。
算法詳解
在上面的圖里伦连，大家很容易就看出來了它的拓?fù)湫颍?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)?strong>只有當(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ì)更精巧哺徊。
在文中為了方便展示室琢，我就用表格了：
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
|---|---|---|---|---|---|---|---|---|---|
| 入度 | 0 | 0 | 2 | 2 | 1 | 2 | 2 | 1 | 1 |
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]放入容器中症汹，
然后想想我們需要哪些操作吧！
我們最常做的操作無非就是把點(diǎn)放進(jìn)來贷腕，把點(diǎn)拿出去執(zhí)行了背镇，也就是需要一個(gè) offer 和 poll 操作比較高效的數(shù)據(jù)結(jié)構(gòu)，那么 queue 就夠用了泽裳。
（其他的也行瞒斩，放進(jìn)來這個(gè)容器里的頂點(diǎn)的地位都是一樣的，都是可以執(zhí)行的涮总，和進(jìn)來的順序無關(guān)胸囱，但何必非得給自己找麻煩呢？一個(gè)常規(guī)順序的簡簡單單的 queue 就夠用了瀑梗。）
然后就需要把某些點(diǎn)拿出去執(zhí)行了烹笔。
【劃重點(diǎn)】當(dāng)我們把 C1 拿出來執(zhí)行，那這意味這什么夺克？
<span style="display:block;color:blue;">答：意味著「以 C1 為頂點(diǎn)」的「指向其他點(diǎn)」的「邊」都消失了箕宙，也就是 C1 的出度變成了 0.
如下圖嚎朽，也就是這兩條邊可以消失了铺纽。
那么此時(shí)我們就可以更新 C1 所指向的那些點(diǎn)也就是 C3 和 C8 的 入度 了，更新后的數(shù)組如下：
| C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
|---|---|---|---|---|---|---|---|
| 入度 | 1 | 2 | 1 | 2 | 2 | <span style="display:block;color:blue;">0 | 1 |
<span style="display:block;color:blue;">那我們這里看到很關(guān)鍵的一步哟忍，C8 的入度變成了 0狡门！
也就意味著 C8 此時(shí)沒有了任何依賴，可以放到我們的 queue 里等待執(zhí)行了锅很。
此時(shí)我們的 queue 里就是：[C2, C8].
Step2
下一個(gè)我們?cè)賵?zhí)行 C2其馏，
那么 C2 所指向的 C3, C5 的 入度-1，
更新表格：
| C3 | C4 | C5 | C6 | C7 | C9 | |
|---|---|---|---|---|---|---|
| 入度 | <span style="display:block;color:blue;">0 | 2 | <span style="display:block;color:blue;">0 | 2 | 2 | 1 |
也就是 C3 和 C5 都沒有了任何束縛爆安，可以放進(jìn) queue 里執(zhí)行了叛复。
queue 此時(shí)變成：[C8, C3, C5]
Step3
那么下一步我們執(zhí)行 C8，
相應(yīng)的 C8 所指的 C9 的入度-1.
更新表格：
| C4 | C6 | C7 | C9 | |
|---|---|---|---|---|
| 入度 | 2 | 2 | 2 | <span style="display:block;color:blue;">0 |
那么 C9 沒有了任何要求，可以放進(jìn) queue 里執(zhí)行了褐奥。
queue 此時(shí)變成：[C3, C5, C9]
Step4
接下來執(zhí)行 C3咖耘，
相應(yīng)的 C3 所指的 C4 的入度-1.
更新表格：
| C4 | C6 | C7 | |
|---|---|---|---|
| 入度 | <span style="display:block;color:blue;">1 | 2 | 2 |
<span style="display:block;color:blue;">但是 C4 的入度并沒有變成 0，所以這一步?jīng)]有任何點(diǎn)可以加入 queue.
queue 此時(shí)變成 [C5, C9]
Step5
再執(zhí)行 C5撬码，
那么 C5 所指的 C4 和 C6 的入度- 1.
更新表格：
| C4 | C6 | C7 | |
|---|---|---|---|
| 入度 | <span style="display:block;color:blue;">0 | <span style="display:block;color:blue;">1 | 2 |
這里 C4 的依賴全都消失啦儿倒，那么可以把 C4 放進(jìn) queue 里了：
queue = [C9, C4]
Step6
然后執(zhí)行 C9，
那么 C9 所指的 C7 的入度- 1.
| C6 | C7 | |
|---|---|---|
| 入度 | <span style="display:block;color:blue;">1 | <span style="display:block;color:blue;">1 |
這里 C7 的入度并不為 0呜笑，還不能加入 queue夫否，
此時(shí) queue = [C4]
Step7
接著執(zhí)行 C4，
所以 C4 所指向的 C6 和 C7 的入度-1叫胁，
更新表格：
| C6 | C7 | |
|---|---|---|
| 入度 | <span style="display:block;color:blue;">0 | <span style="display:block;color:blue;">0 |
C6 和 C7 的入度都變成 0 啦；舜取！把它們放入 queue曹抬，繼續(xù)執(zhí)行到直到 queue 為空即可溉瓶。
總結(jié)
好了，那我們梳理一下這個(gè)算法：
<span style="display:block;color:blue;">數(shù)據(jù)結(jié)構(gòu)
這里我們的入度表格可以用 map 來存放谤民，關(guān)于 map 還有不清楚的同學(xué)可以看之前我寫的 HashMap 的文章哦～
Map: <key = Vertex, value = 入度>
但實(shí)際代碼中堰酿，我們用一個(gè) int array 來存儲(chǔ)也就夠了，graph node 可以用數(shù)組的 index 來表示张足，value 就用數(shù)組里的數(shù)值來表示触创，這樣比 Map 更精巧。
然后用了一個(gè)普通的 queue为牍，用來存放可以被執(zhí)行的那些 node.
<span style="display:block;color:blue;">過程
我們把入度為 0 的那些頂點(diǎn)放入 queue 中哼绑，然后通過每次執(zhí)行 queue 中的頂點(diǎn)，就可以讓依賴這個(gè)被執(zhí)行的頂點(diǎn)的那些點(diǎn)的 入度-1碉咆，如果有頂點(diǎn)的入度變成了 0抖韩，就可以放入 queue 了，直到 queue 為空疫铜。
<span style="display:block;color:blue;">細(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 的條件的話席揽，那么有可能是不存在可行解的，那怎么判斷呢谓厘？很簡單的一個(gè)方法就是比較一下最后結(jié)果中的頂點(diǎn)的個(gè)數(shù)和圖中所有頂點(diǎn)的個(gè)數(shù)是否相等幌羞，或者加個(gè)計(jì)數(shù)器，如果不相等竟稳，說明就不存在有效解属桦。所以這個(gè)算法也可以用來判斷一個(gè)圖是不是有向無環(huán)圖熊痴。
很多題目給的條件可能是給這個(gè)圖的 edge list，也是表示圖的一種常用的方式聂宾。那么給的這個(gè) list 就是表示圖中的邊愁拭。這里要注意審題哦，看清楚是誰 depends on 誰亏吝。其實(shí)圖的題一般都不會(huì)直接給你這個(gè)圖岭埠，而是給一個(gè)場景，需要你把它變回一個(gè)圖蔚鸥。
<span style="display:block;color:blue;">時(shí)間復(fù)雜度
注意 ??：對(duì)于圖的時(shí)間復(fù)雜度分析一定是兩個(gè)參數(shù)惜论，面試的時(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)
<span style="display:block;color:blue;">空間復(fù)雜度
用了一個(gè)數(shù)組來存所有點(diǎn)的 indegree销睁，之后的 queue 也是最多把所有的點(diǎn)放進(jìn)去供璧，所以是 O(v).
<span style="display:block;color:blue;">代碼
關(guān)于這課程排序的問題，Leetcode 上有兩道題冻记，一道是 207睡毒，問你能否完成所有課程，也就是問拓?fù)渑判蚴欠翊嬖谌呃酰涣硪坏朗?210 題演顾，是讓你返回任意一個(gè)拓?fù)漤樞颍绻荒芡瓿烧曷鳎蔷头祷匾粋€(gè)空 array偶房。
這里我們以 210 這道題來寫趁曼，更完整也更尘考一些。
這里給的 input 就是我們剛剛說到的 edge list.
Example 1.
Input: 2, [[1,0]]
Output: [0,1]
Explanation: 這里一共 2 門課挡闰，1 的先修課程是 0. 所以正確的選課順序是[0, 1].
Example 2.
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: 這課沒法上了
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] res = new int[numCourses];
int[] indegree = new int[numCourses];
// get the indegree for each course
for(int[] pre : prerequisites) {
indegree[pre[0]] ++;
}
// put courses with indegree == 0 to queue
Queue<Integer> queue = new ArrayDeque<>();
for(int i = 0; i < numCourses; i++) {
if(indegree[i] == 0) {
queue.offer(i);
}
}
// execute the course
int i = 0;
while(!queue.isEmpty()) {
Integer curr = queue.poll();
res[i++] = curr;
// remove the pre = curr
for(int[] pre : prerequisites) {
if(pre[1] == curr) {
indegree[pre[0]] --;
if(indegree[pre[0]] == 0) {
queue.offer(pre[0]);
}
}
}
}
return i == numCourses ? res : new int[]{};
}
}
另外乒融，拓?fù)渑判蜻€可以用 DFS - 深度優(yōu)先搜索 來實(shí)現(xiàn)掰盘，限于篇幅就不在這里展開了，大家可以參考GeeksforGeeks的這個(gè)資料赞季。
實(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)具有最大長度的路徑稱為關(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í)間。
具體是怎么應(yīng)用分析的层释，大家可以參考這個(gè)視頻 的 14 分 46 秒征椒，這個(gè)例子還是講的很好的。
其實(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)用，比如說：
- 語音識(shí)別系統(tǒng)的預(yù)處理马澈；
- 管理目標(biāo)文件之間的依賴關(guān)系瓢省，就像我剛剛說的 jar 包導(dǎo)入；
- 深度學(xué)習(xí)中的網(wǎng)絡(luò)結(jié)構(gòu)處理痊班。
如有其他補(bǔ)充勤婚，歡迎大家在評(píng)論區(qū)不吝賜教。
以上就是本文的全部內(nèi)容了涤伐，拓?fù)渑判蚴欠浅Ｖ匾彩欠浅劭嫉囊活愃惴ǎ嬖嚧髲S前一定要熟練掌握缨称。
如果你喜歡這篇文章，記得給我點(diǎn)贊留言哦～你們的支持和認(rèn)可祝迂，就是我創(chuàng)作的最大動(dòng)力睦尽，我們下篇文章見！
我是小齊型雳，紐約程序媛当凡，終生學(xué)習(xí)者，每天晚上 9 點(diǎn)纠俭，云自習(xí)室里不見不散宁玫！
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE
