拓?fù)渑判?，YYDS！
[導(dǎo)讀]讀完本文，可以去力扣解決如下題目：207.課程表（Medium）210.課程表II（Medium）很多讀者留言說(shuō)要看「圖」相關(guān)的算法，那就滿足大家，結(jié)合算法題把圖相關(guān)的技巧給大家過(guò)一遍。數(shù)據(jù)結(jié)構(gòu)相關(guān)的算法無(wú)非兩點(diǎn)：遍歷訪問(wèn)。那么圖的基本遍歷方法也很簡(jiǎn)單，以前就講過(guò)如何從多叉樹(shù)的遍...
讀完本文，可以去力扣解決如下題目：207.課程表（Medium）210.課程表 II（Medium）很多讀者留言說(shuō)要看「圖」相關(guān)的算法，那就滿足大家，結(jié)合算法題把圖相關(guān)的技巧給大家過(guò)一遍。
數(shù)據(jù)結(jié)構(gòu)相關(guān)的算法無(wú)非兩點(diǎn)：遍歷 訪問(wèn)。那么圖的基本遍歷方法也很簡(jiǎn)單，以前就講過(guò)如何從多叉樹(shù)的遍歷框架擴(kuò)展到圖的遍歷。圖這種數(shù)據(jù)結(jié)構(gòu)還有一些比較特殊的算法，比如二分圖判斷，有環(huán)圖無(wú)環(huán)圖的判斷，拓?fù)?/a>排序，以及最經(jīng)典的最小生成樹(shù)，單源最短路徑問(wèn)題，更難的就是類(lèi)似網(wǎng)絡(luò)流這樣的問(wèn)題。不過(guò)以我的經(jīng)驗(yàn)?zāi)?，像網(wǎng)絡(luò)流這種問(wèn)題，你又不是打競(jìng)賽的，除非自己特別有興趣，否則就沒(méi)必要學(xué)了；像最小生成樹(shù)和最短路徑問(wèn)題，雖然從刷題的角度用到的不多，但它們屬于經(jīng)典算法，學(xué)有余力可以掌握一下；像拓?fù)渑判蜻@一類(lèi)，屬于比較基本且有用的算法，應(yīng)該比較熟練地掌握。那么本文就結(jié)合具體的算法題，來(lái)說(shuō)說(shuō)拓?fù)渑判蛩惴ㄔ恚?/strong>因?yàn)橥負(fù)渑判虻膶?duì)象是有向無(wú)環(huán)圖，所以順帶說(shuō)一下如何判斷圖是否有環(huán)。
數(shù)據(jù)結(jié)構(gòu)相關(guān)的算法無(wú)非兩點(diǎn)：遍歷 訪問(wèn)。那么圖的基本遍歷方法也很簡(jiǎn)單，以前就講過(guò)如何從多叉樹(shù)的遍歷框架擴(kuò)展到圖的遍歷。圖這種數(shù)據(jù)結(jié)構(gòu)還有一些比較特殊的算法，比如二分圖判斷，有環(huán)圖無(wú)環(huán)圖的判斷，拓?fù)?/a>排序，以及最經(jīng)典的最小生成樹(shù)，單源最短路徑問(wèn)題，更難的就是類(lèi)似網(wǎng)絡(luò)流這樣的問(wèn)題。不過(guò)以我的經(jīng)驗(yàn)?zāi)?，像網(wǎng)絡(luò)流這種問(wèn)題，你又不是打競(jìng)賽的，除非自己特別有興趣，否則就沒(méi)必要學(xué)了；像最小生成樹(shù)和最短路徑問(wèn)題，雖然從刷題的角度用到的不多，但它們屬于經(jīng)典算法，學(xué)有余力可以掌握一下；像拓?fù)渑判蜻@一類(lèi)，屬于比較基本且有用的算法，應(yīng)該比較熟練地掌握。那么本文就結(jié)合具體的算法題，來(lái)說(shuō)說(shuō)拓?fù)渑判蛩惴ㄔ恚?/strong>因?yàn)橥負(fù)渑判虻膶?duì)象是有向無(wú)環(huán)圖，所以順帶說(shuō)一下如何判斷圖是否有環(huán)。
判斷有向圖是否存在環(huán)
先來(lái)看看力扣第 207 題「課程表」：int[]?findOrder(int?numCourses,?int[][]?prerequisites);
題目應(yīng)該不難理解，什么時(shí)候無(wú)法修完所有課程？當(dāng)存在循環(huán)依賴(lài)的時(shí)候。其實(shí)這種場(chǎng)景在現(xiàn)實(shí)生活中也十分常見(jiàn)，比如我們寫(xiě)代碼 import 包也是一個(gè)例子，必須合理設(shè)計(jì)代碼目錄結(jié)構(gòu)，否則會(huì)出現(xiàn)循環(huán)依賴(lài)，編譯器會(huì)報(bào)錯(cuò)，所以編譯器實(shí)際上也使用了類(lèi)似算法來(lái)判斷你的代碼是否能夠成功編譯。看到依賴(lài)問(wèn)題，首先想到的就是把問(wèn)題轉(zhuǎn)化成「有向圖」這種數(shù)據(jù)結(jié)構(gòu)，只要圖中存在環(huán)，那就說(shuō)明存在循環(huán)依賴(lài)。具體來(lái)說(shuō)，我們首先可以把課程看成「有向圖」中的節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)分別是0, 1, ..., numCourses-1，把課程之間的依賴(lài)關(guān)系看做節(jié)點(diǎn)之間的有向邊。比如說(shuō)必須修完課程1才能去修課程3，那么就有一條有向邊從節(jié)點(diǎn)1指向3。所以我們可以根據(jù)題目輸入的prerequisites數(shù)組生成一幅類(lèi)似這樣的圖：List[]?graph;
graph[s]是一個(gè)列表，存儲(chǔ)著節(jié)點(diǎn)s所指向的節(jié)點(diǎn)。所以我們首先可以寫(xiě)一個(gè)建圖函數(shù)：List[]?buildGraph(int?numCourses,?int[][]?prerequisites)?{
????//?圖中共有?numCourses?個(gè)節(jié)點(diǎn)
????List[]?graph?=?new?LinkedList[numCourses];
????for?(int?i?=?0;?i?????????graph[i]?=?new?LinkedList<>();
????}
????for?(int[]?edge?:?prerequisites)?{
????????int?from?=?edge[1];
????????int?to?=?edge[0];
????????//?修完課程?from?才能修課程?to
????????//?在圖中添加一條從?from?指向?to?的有向邊
????????graph[from].add(to);
????}
????return?graph;
}
圖建出來(lái)了，怎么判斷圖中有沒(méi)有環(huán)呢？先不要急，我們先來(lái)思考如何遍歷這幅圖，只要會(huì)遍歷，就可以判斷圖中是否存在環(huán)了。前文 圖論基礎(chǔ) 寫(xiě)了 DFS 算法遍歷圖的框架，無(wú)非就是從多叉樹(shù)遍歷框架擴(kuò)展出來(lái)的，加了個(gè)visited數(shù)組罷了：//?防止重復(fù)遍歷同一個(gè)節(jié)點(diǎn)
boolean[]?visited;
//?從節(jié)點(diǎn)?s?開(kāi)始?BFS?遍歷，將遍歷過(guò)的節(jié)點(diǎn)標(biāo)記為?true
void?traverse(List[]?graph,?int?s) ?{
????if?(visited[s])?{
????????return;
????}
????/*?前序遍歷代碼位置?*/
????//?將當(dāng)前節(jié)點(diǎn)標(biāo)記為已遍歷
????visited[s]?=?true;
????for?(int?t?:?graph[s])?{
????????traverse(graph,?t);
????}
????/*?后序遍歷代碼位置?*/
}
那么我們就可以直接套用這個(gè)遍歷代碼：//?防止重復(fù)遍歷同一個(gè)節(jié)點(diǎn)
boolean[]?visited;
boolean?canFinish(int?numCourses,?int[][]?prerequisites)?{
????List[]?graph?=?buildGraph(numCourses,?prerequisites);
????visited?=?new?boolean[numCourses];
????for?(int?i?=?0;?i?????????traverse(graph,?i);
????}
}
void?traverse(List[]?graph,?int?s) ?{
????//?代碼見(jiàn)上文
}
注意圖中并不是所有節(jié)點(diǎn)都相連，所以要用一個(gè) for 循環(huán)將所有節(jié)點(diǎn)都作為起點(diǎn)調(diào)用一次 DFS 搜索算法。這樣，就能遍歷這幅圖中的所有節(jié)點(diǎn)了，你打印一下visited數(shù)組，應(yīng)該全是 true。我曾經(jīng)說(shuō)過(guò)，圖的遍歷和遍歷多叉樹(shù)差不多，所以到這里你應(yīng)該都能很容易理解。那么如何判斷這幅圖中是否存在環(huán)呢？你可以把遞歸函數(shù)看成一個(gè)在遞歸樹(shù)上游走的指針，這里也是類(lèi)似的：你也可以把traverse看做在圖中節(jié)點(diǎn)上游走的指針，只需要再添加一個(gè)布爾數(shù)組onPath記錄當(dāng)前traverse經(jīng)過(guò)的路徑：boolean[]?onPath;
boolean?hasCycle?=?false;
boolean[]?visited;
void?traverse(List[]?graph,?int?s) ?{
????if?(onPath[s])?{
????????//?發(fā)現(xiàn)環(huán)！??！
????????hasCycle?=?true;
????}
????if?(visited[s])?{
????????return;
????}
????//?將節(jié)點(diǎn)?s?標(biāo)記為已遍歷
????visited[s]?=?true;
????//?開(kāi)始遍歷節(jié)點(diǎn)?s
????onPath[s]?=?true;
????for?(int?t?:?graph[s])?{
????????traverse(graph,?t);
????}
????//?節(jié)點(diǎn)?s?遍歷完成
????onPath[s]?=?false;
}
這里就有點(diǎn)回溯算法的味道了，在進(jìn)入節(jié)點(diǎn)s的時(shí)候?qū)?code style="font-size: inherit;line-height: inherit;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(233, 105, 0);background: rgb(248, 248, 248);">onPath[s]標(biāo)記為 true，離開(kāi)時(shí)標(biāo)記回 false，如果發(fā)現(xiàn)onPath[s]已經(jīng)被標(biāo)記，說(shuō)明出現(xiàn)了環(huán)。PS：參考貪吃蛇沒(méi)繞過(guò)彎兒咬到自己的場(chǎng)景。這樣，就可以在遍歷圖的過(guò)程中順便判斷是否存在環(huán)了，完整代碼如下：//?記錄一次?traverse?遞歸經(jīng)過(guò)的節(jié)點(diǎn)
boolean[]?onPath;
//?記錄遍歷過(guò)的節(jié)點(diǎn)，防止走回頭路
boolean[]?visited;
//?記錄圖中是否有環(huán)
boolean?hasCycle?=?false;
boolean?canFinish(int?numCourses,?int[][]?prerequisites)?{
????List[]?graph?=?buildGraph(numCourses,?prerequisites);
????visited?=?new?boolean[numCourses];
????onPath?=?new?boolean[numCourses];
????for?(int?i?=?0;?i?????????//?遍歷圖中的所有節(jié)點(diǎn)
????????traverse(graph,?i);
????}
????//?只要沒(méi)有循環(huán)依賴(lài)可以完成所有課程
????return?!hasCycle;
}
void?traverse(List[]?graph,?int?s) ?{
????if?(onPath[s])?{
????????//?出現(xiàn)環(huán)
????????hasCycle?=?true;
????}
????if?(visited[s]?||?hasCycle)?{
????????//?如果已經(jīng)找到了環(huán)，也不用再遍歷了
????????return;
????}
????//?前序遍歷代碼位置
????visited[s]?=?true;
????onPath[s]?=?true;
????for?(int?t?:?graph[s])?{
????????traverse(graph,?t);
????}
????//?后序遍歷代碼位置
????onPath[s]?=?false;
}
List[]?buildGraph(int?numCourses,?int[][]?prerequisites)?{
????//?代碼見(jiàn)前文
}
這道題就解決了，核心就是判斷一幅有向圖中是否存在環(huán)。不過(guò)如果出題人繼續(xù)惡心你，讓你不僅要判斷是否存在環(huán)，還要返回這個(gè)環(huán)具體有哪些節(jié)點(diǎn)，怎么辦？你可能說(shuō)，onPath里面為 true 的索引，不就是組成環(huán)的節(jié)點(diǎn)編號(hào)嗎？不是的，假設(shè)下圖中綠色的節(jié)點(diǎn)是遞歸的路徑，它們?cè)?code style="font-size: inherit;line-height: inherit;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(233, 105, 0);background: rgb(248, 248, 248);">onPath中的值都是 true，但顯然成環(huán)的節(jié)點(diǎn)只是其中的一部分：拓?fù)渑判?/span>
看下力扣第 210 題「課程表 II」：int[]?findOrder(int?numCourses,?int[][]?prerequisites);
這里我先說(shuō)一下拓?fù)渑判颍═opological Sorting）這個(gè)名詞，網(wǎng)上搜出來(lái)的定義很數(shù)學(xué)，這里干脆用百度百科的一幅圖來(lái)讓你直觀地感受下：public?int[]?findOrder(int?numCourses,?int[][]?prerequisites)?{
????if?(!canFinish(numCourses,?prerequisites))?{
????????//?不可能完成所有課程
????????return?new?int[]{};
????}
????//?...
}
PS：簡(jiǎn)單起見(jiàn)，canFinish?直接復(fù)用了之前實(shí)現(xiàn)的函數(shù)，但實(shí)際上可以把環(huán)檢測(cè)的邏輯和拓?fù)渑判虻倪壿嫿Y(jié)合起來(lái)，同時(shí)在 traverse 函數(shù)里完成，這個(gè)可以留給大家自己去實(shí)現(xiàn)。那么關(guān)鍵問(wèn)題來(lái)了，如何進(jìn)行拓?fù)渑判颍?/span>是不是又要秀什么高大上的技巧了？其實(shí)特別簡(jiǎn)單，將后序遍歷的結(jié)果進(jìn)行反轉(zhuǎn)，就是拓?fù)渑判虻慕Y(jié)果。直接看解法代碼：boolean[]?visited;
//?記錄后序遍歷結(jié)果
List?postorder?=?new?ArrayList<>();
int[]?findOrder(int?numCourses,?int[][]?prerequisites)?{
????//?先保證圖中無(wú)環(huán)
????if?(!canFinish(numCourses,?prerequisites))?{
????????return?new?int[]{};
????}
????//?建圖
????List[]?graph?=?buildGraph(numCourses,?prerequisites);
????//?進(jìn)行?DFS?遍歷
????visited?=?new?boolean[numCourses];
????for?(int?i?=?0;?i?????????traverse(graph,?i);
????}
????//?將后序遍歷結(jié)果反轉(zhuǎn)，轉(zhuǎn)化成?int[]?類(lèi)型
????Collections.reverse(postorder);
????int[]?res?=?new?int[numCourses];
????for?(int?i?=?0;?i?????????res[i]?=?postorder.get(i);
????}
????return?res;
}
void?traverse(List[]?graph,?int?s) ?{
????if?(visited[s])?{
????????return;
????}
????visited[s]?=?true;
????for?(int?t?:?graph[s])?{
????????traverse(graph,?t);
????}
????//?后序遍歷位置
????postorder.add(s);
}
//?參考上一題的解法
boolean?canFinish(int?numCourses,?int[][]?prerequisites);
//?參考前文代碼
List[]?buildGraph(int?numCourses,?int[][]?prerequisites);
代碼雖然看起來(lái)多，但是邏輯應(yīng)該是很清楚的，只要圖中無(wú)環(huán)，那么我們就調(diào)用traverse函數(shù)對(duì)圖進(jìn)行 BFS 遍歷，記錄后序遍歷結(jié)果，最后把后序遍歷結(jié)果反轉(zhuǎn)，作為最終的答案。那么為什么后序遍歷的反轉(zhuǎn)結(jié)果就是拓?fù)渑判蚰?/strong>？我這里也避免數(shù)學(xué)證明，用一個(gè)直觀地例子來(lái)解釋?zhuān)覀兙驼f(shuō)二叉樹(shù)，這是我們說(shuō)過(guò)很多次的二叉樹(shù)遍歷框架：void?traverse(TreeNode?root)?{
????//?前序遍歷代碼位置
????traverse(root.left)
????//?中序遍歷代碼位置
????traverse(root.right)
????//?后序遍歷代碼位置
}
二叉樹(shù)的后序遍歷是什么時(shí)候？遍歷完左右子樹(shù)之后才會(huì)執(zhí)行后序遍歷位置的代碼。換句話說(shuō)，當(dāng)左右子樹(shù)的節(jié)點(diǎn)都被裝到結(jié)果列表里面了，根節(jié)點(diǎn)才會(huì)被裝進(jìn)去。后序遍歷的這一特點(diǎn)很重要，之所以拓?fù)渑判虻幕A(chǔ)是后序遍歷，是因?yàn)橐粋€(gè)任務(wù)必須在等到所有的依賴(lài)任務(wù)都完成之后才能開(kāi)始開(kāi)始執(zhí)行。你把每個(gè)任務(wù)理解成二叉樹(shù)里面的節(jié)點(diǎn)，這個(gè)任務(wù)所依賴(lài)的任務(wù)理解成子節(jié)點(diǎn)，那你是不是應(yīng)該先把所有子節(jié)點(diǎn)處理完再處理父節(jié)點(diǎn)？這是不是就是后序遍歷？下圖是一個(gè)二叉樹(shù)的后序遍歷結(jié)果：結(jié)合這個(gè)圖說(shuō)一說(shuō)為什么還要把后序遍歷結(jié)果反轉(zhuǎn)，才是最終的拓?fù)渑判蚪Y(jié)果。我們說(shuō)一個(gè)節(jié)點(diǎn)可以理解為一個(gè)任務(wù)，這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)理解為這個(gè)任務(wù)的依賴(lài)，但你注意我們之前說(shuō)的依賴(lài)關(guān)系的表示：如果做完A才能去做B，那么就有一條從A指向B的有向邊，表示B依賴(lài)A。那么，父節(jié)點(diǎn)依賴(lài)子節(jié)點(diǎn)，體現(xiàn)在二叉樹(shù)里面應(yīng)該是這樣的：
下載文檔
