如果有人正在準(zhǔn)備算法面試我建議一定不要跳過(guò)LeetCode 207這道Course Schedule。它是圖論里“有向圖找環(huán)”最標(biāo)準(zhǔn)的入門題也是一個(gè)非常經(jīng)典的“外表是課程表、內(nèi)核是圖模型”的面試題。題目會(huì)給你numCourses門課程以及一組先修關(guān)系prerequisites其中[a, b]表示要先修b才能修a問(wèn)能不能把這些課程全部修完。把這組依賴關(guān)系看成一張有向圖問(wèn)題瞬間就能翻譯成這張圖里是否存在環(huán)。存在環(huán)意味著課程互相依賴永遠(yuǎn)排不出合法順序不存在環(huán)所有課程才能逐步完成。這題最主流的兩種解法一種是DFS遞歸配合“三色標(biāo)記”另一種是拓?fù)渑判虻腒ahn算法迭代。這兩種解法我都建議不要只背模板而是徹底弄懂它們各自判定環(huán)的原理。下面我會(huì)從建模開(kāi)始把兩條思路完整拆開(kāi)再結(jié)合面試場(chǎng)景聊一聊怎么選擇、怎么避免翻車。1. 題目解讀從課程表到有向圖建模1.1 題目到底在問(wèn)什么先看一個(gè)具體例子。numCourses 2prerequisites [[1, 0]]。這里的含義是要學(xué)課程1必須先學(xué)課程0也就是存在一條從0指向1的有向邊。因?yàn)?可以正常修完再修1所以答案是true。再看numCourses 2prerequisites [[1, 0], [0, 1]]意思是課程1依賴0課程0又依賴1形成了環(huán)。這種情況下哪門課都沒(méi)法“先修”所以答案是false。這類題目還有一個(gè)容易忽略的地方numCourses門課并不一定彼此關(guān)聯(lián)。有些課可能完全沒(méi)有任何先修關(guān)系有些課可能是其他課的“前置課程”但自己沒(méi)有任何前置。LeetCode這類題的測(cè)試用例里空依賴、孤立節(jié)點(diǎn)、多組互不影響的分量都很常見(jiàn)。如果你寫的解法只從一個(gè)節(jié)點(diǎn)出發(fā)或者只用局部信息判斷很容易漏判。1.2 建模方式鄰接表和有向邊的方向看到先修關(guān)系第一步就是建圖。這里最推薦用鄰接表而不是鄰接矩陣。鄰接表在每個(gè)節(jié)點(diǎn)下掛一個(gè)列表存它所有“直接后繼”。對(duì)應(yīng)到本題adj [[] for _ in range(numCourses)] for cur, pre in prerequisites: adj[pre].append(cur)注意方向是pre指向cur也就是“先修課指向后續(xù)課”。這個(gè)方向一旦定下來(lái)后面DFS和Kahn里的“鄰居”“入度”都要全部基于它來(lái)理解。如果方向建反了代碼可能不會(huì)立刻報(bào)錯(cuò)但邏輯會(huì)完全錯(cuò)位。在實(shí)際面試?yán)镂乙?jiàn)過(guò)太多人一開(kāi)始沒(méi)想清楚寫完才發(fā)現(xiàn)漏洞。為什么用鄰接表因?yàn)閜rerequisites的規(guī)模通常遠(yuǎn)小于numCourses的平方屬于稀疏圖。用二維矩陣不僅要浪費(fèi)大量?jī)?nèi)存遍歷某個(gè)課程的全部后繼時(shí)也特別麻煩。鄰接表在構(gòu)建和遍歷上都是O(V E)是圖論題最常用的數(shù)據(jù)結(jié)構(gòu)。1.3 為什么核心就是“有向圖找環(huán)”課程能不能全部完成本質(zhì)上就是依賴圖能不能全序化。一個(gè)無(wú)環(huán)有向圖DAG一定存在至少一種拓?fù)渑判蚨灰獔D里有環(huán)環(huán)上的節(jié)點(diǎn)誰(shuí)都無(wú)法先被滿足也就不存在合法順序。所以判定“能否完成全部課程”和判定“這張有向圖是否有環(huán)”是同一件事。這里還有一層值得向面試官說(shuō)明的含義題目只要求判斷能否完成并不要求輸出具體的課程順序。所以你不需要真的排一個(gè)拓?fù)湫蛄兄灰袛唷澳懿荒芘拧?。這也是為什么DFS和Kahn都可以做到提前返回false而不必等全部遍歷結(jié)束。2. 解法一DFS遞歸 三色標(biāo)記2.1 核心思想把“訪問(wèn)中”和“訪問(wèn)完”分開(kāi)很多人一看到判環(huán)第一反應(yīng)是維護(hù)一個(gè)布爾visited數(shù)組。但實(shí)際上只用visited非常容易誤判。原因在于DFS會(huì)回溯。某個(gè)節(jié)點(diǎn)可能先在一個(gè)分支里被訪問(wèn)完之后另一個(gè)分支再路過(guò)它這屬于正常的復(fù)用并不代表出現(xiàn)環(huán)。真正需要抓的是在“當(dāng)前這次遞歸路徑”上是否又一次經(jīng)過(guò)了同一個(gè)節(jié)點(diǎn)。我習(xí)慣用三色狀態(tài)去解決0尚未訪問(wèn)過(guò)1正在當(dāng)前遞歸路徑中也就是灰色狀態(tài)2已經(jīng)完整處理完且確認(rèn)這個(gè)節(jié)點(diǎn)所在的下游沒(méi)有環(huán)DFS遞歸時(shí)如果發(fā)現(xiàn)鄰居的狀態(tài)是1說(shuō)明又繞回了當(dāng)前路徑上的某個(gè)節(jié)點(diǎn)這是環(huán)的直接證據(jù)如果發(fā)現(xiàn)狀態(tài)是2說(shuō)明之前已經(jīng)驗(yàn)證過(guò)這顆子樹(shù)安全直接跳過(guò)即可。用0/1/2三個(gè)整數(shù)值比維護(hù)visited和onPath兩個(gè)布爾數(shù)組更簡(jiǎn)潔也更容易在面試時(shí)解釋清楚。2.2 完整代碼與逐行拆解from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: # 鄰接表pre - [cur1, cur2, ...] adj [[] for _ in range(numCourses)] for cur, pre in prerequisites: adj[pre].append(cur) # 0 未訪問(wèn)1 正在當(dāng)前遞歸路徑上2 已確認(rèn)安全 state [0] * numCourses def dfs(node: int) - bool: if state[node] 1: # 又回到當(dāng)前路徑上的節(jié)點(diǎn)意味著有環(huán) return False if state[node] 2: # 之前已經(jīng)確認(rèn)過(guò)安全直接放行 return True # 進(jìn)入遞歸標(biāo)記灰色 state[node] 1 for nxt in adj[node]: if not dfs(nxt): return False # 所有下游都安全標(biāo)記黑色 state[node] 2 return True for course in range(numCourses): if not dfs(course): return False return True代碼看起來(lái)不長(zhǎng)但有幾個(gè)點(diǎn)需要特別關(guān)注。第一外層循環(huán)必須遍歷所有課程不能只從有依賴的節(jié)點(diǎn)出發(fā)否則孤立節(jié)點(diǎn)或單獨(dú)一片連通子圖可能被漏掉。第二state[node] 2這句放在for循環(huán)之后表示只有當(dāng)前節(jié)點(diǎn)的所有鄰居都返回True才能把當(dāng)前節(jié)點(diǎn)標(biāo)記為安全。第三一旦dfs返回False整個(gè)函數(shù)就提前結(jié)束不需要再恢復(fù)state這也是“提前剪枝”的一種體現(xiàn)。2.3 復(fù)雜度推導(dǎo)與遞歸深度風(fēng)險(xiǎn)時(shí)間復(fù)雜度上每個(gè)節(jié)點(diǎn)最多訪問(wèn)一次每條邊最多遍歷一次構(gòu)建鄰接表本身也是O(E)所以整體是O(V E)其中V是課程數(shù)E是先修關(guān)系數(shù)?？臻g上需要存鄰接表還需要state數(shù)組和遞歸調(diào)用棧整體也是O(V E)。但是Python的遞歸深度默認(rèn)值大概在1000左右。如果測(cè)試數(shù)據(jù)構(gòu)造了一條很長(zhǎng)的依賴鏈比如0 - 1 - 2 - ...遞歸深度可能直接超過(guò)限制拋出RuntimeError。這個(gè)錯(cuò)誤有時(shí)候會(huì)被誤認(rèn)為“這段代碼處理不了大用例”其實(shí)是單純因?yàn)檫f歸棧深度。我的習(xí)慣是在正式提交前加兩行import sys sys.setrecursionlimit(10000)這種做法不改變算法正確性只是提前把上限調(diào)高防止測(cè)試數(shù)據(jù)里出現(xiàn)深鏈時(shí)意外爆棧。面試時(shí)如果環(huán)境不方便改也可以主動(dòng)提一句“實(shí)際題目數(shù)據(jù)一般不會(huì)太深但我傾向于先調(diào)遞歸上限”展示你了解這個(gè)風(fēng)險(xiǎn)。2.4 我實(shí)際調(diào)試時(shí)遇到的反直覺(jué)坑三色標(biāo)記本身思路清晰但實(shí)現(xiàn)細(xì)節(jié)里容易踩坑。有一個(gè)非常常見(jiàn)的錯(cuò)誤是外層循環(huán)寫了range(numCourses)但dfs內(nèi)部偷懶只處理鄰接表非空的節(jié)點(diǎn)或者忽略孤立節(jié)點(diǎn)。這樣大部分用例能過(guò)但遇到一些特殊構(gòu)造就會(huì)出問(wèn)題。比較穩(wěn)的做法是傳入任何節(jié)點(diǎn)都嚴(yán)格按照三色邏輯走一遍狀態(tài)為1返回False狀態(tài)為2返回True否則標(biāo)記1并遞歸。另一個(gè)反直覺(jué)的地方是自環(huán)比如prerequisites [[1, 1]]。按題意課程1先修自己幾乎不可能但作為穩(wěn)健的程序員代碼最好能扛住這種輸入。DFS解法里自環(huán)會(huì)讓當(dāng)前節(jié)點(diǎn)在遞歸時(shí)以state 1的狀態(tài)再次出現(xiàn)直接返回False所以能正確處理。Kahn解法同樣能識(shí)別自環(huán)后面會(huì)講到。3. 解法二Kahn拓?fù)渑判蚣兊挥眠f歸3.1 核心思想入度為0的課程一定可以立刻學(xué)Kahn算法有一個(gè)非常直觀的出發(fā)點(diǎn)如果一門課程沒(méi)有任何先修課程它的入度就為0這門課現(xiàn)在就可以學(xué)。學(xué)完之后它會(huì)解除所有后續(xù)課程的一個(gè)依賴限制于是這些后續(xù)課程的入度各自減1。當(dāng)某個(gè)后續(xù)課程的入度減到0時(shí)說(shuō)明它的所有前置課都已經(jīng)修完它也能進(jìn)入隊(duì)列。這個(gè)思路就像一層層“剝洋蔥”從沒(méi)有依賴的節(jié)點(diǎn)開(kāi)始不斷移除“已經(jīng)可以完成的課”。最終如果所有課程都被移除說(shuō)明圖無(wú)環(huán)如果隊(duì)列空了但還有課程沒(méi)有被移除說(shuō)明剩下的節(jié)點(diǎn)必然構(gòu)成環(huán)。在一個(gè)有向有限圖中如果剩余節(jié)點(diǎn)每個(gè)入度都大于0那必然至少存在一個(gè)環(huán)因?yàn)檠刂扒膀?qū)”一直回溯總會(huì)在有限步內(nèi)重復(fù)遇到某個(gè)節(jié)點(diǎn)。3.2 完整代碼與逐行拆解from collections import deque from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: adj [[] for _ in range(numCourses)] indegree [0] * numCourses for cur, pre in prerequisites: adj[pre].append(cur) indegree[cur] 1 q deque([i for i in range(numCourses) if indegree[i] 0]) finished 0 while q: course q.popleft() finished 1 for nxt in adj[course]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return finished numCourses初始化隊(duì)列時(shí)一定要掃描全部的numCourses個(gè)節(jié)點(diǎn)把所有入度為0的課程都放進(jìn)去。有些同學(xué)會(huì)忍不住只放“看起來(lái)和依賴關(guān)系相關(guān)的課程”結(jié)果漏掉了孤立節(jié)點(diǎn)導(dǎo)致finished永遠(yuǎn)到不了numCourses誤判成環(huán)。循環(huán)中每彈出一個(gè)課程就代表這門課已經(jīng)可以完成finished加1。接著遍歷它所有的后繼課程把它們的入度減1。如果某個(gè)后繼的入度剛好變成0說(shuō)明它所有前置課都完成了立刻加入隊(duì)列。最終只要看看finished是否等于numCourses即可。3.3 迭代解法的天然優(yōu)勢(shì)Kahn解法完全不用遞歸最直接的好處是不會(huì)遇到爆棧問(wèn)題。Python跑長(zhǎng)鏈輸入時(shí)DFS可能還要擔(dān)心遞歸深度Kahn用一個(gè)隊(duì)列從頭走到尾穩(wěn)定性高很多。它對(duì)“正確性”的證明也更適合面試口述每一步都在模擬一個(gè)合法的選課過(guò)程入度為0的節(jié)點(diǎn)表示當(dāng)前沒(méi)有被未修完的前置課擋住彈出一個(gè)課程并解除它作為前置造成的影響是合理的。如果全部課程都能被彈出自然存在合法順序反之則說(shuō)明剩下的節(jié)點(diǎn)形成了環(huán)。還有一個(gè)隱藏優(yōu)勢(shì)拓?fù)渑判蚝驼n程順序天然對(duì)應(yīng)隊(duì)列里彈出的順序就是一個(gè)合法的課程修讀順序。順著Kahn解法稍微改一點(diǎn)就能解決LeetCode 210這道輸出課程順序的題。詳細(xì)擴(kuò)展我放在后面第4節(jié)講。4. 兩種解法對(duì)比與面試使用策略4.1 直接對(duì)比不廢話對(duì)比維度DFS三色標(biāo)記Kahn拓?fù)渑判虼a主體遞歸函數(shù)while循環(huán)加隊(duì)列判環(huán)的核心依據(jù)回到狀態(tài)為1的節(jié)點(diǎn)出隊(duì)課程數(shù)不等于總數(shù)遞歸爆棧風(fēng)險(xiǎn)有需要調(diào)遞歸上限沒(méi)有理解門檻需要對(duì)遞歸狀態(tài)有清晰認(rèn)識(shí)更貼近“依賴解除”的直覺(jué)擴(kuò)展到輸出課程順序需要額外記錄和逆序出隊(duì)順序就是合法順序面試急救價(jià)值展示圖論細(xì)節(jié)理解時(shí)加分穩(wěn)妥、快速、不易寫錯(cuò)4.2 面試時(shí)先說(shuō)哪套更合適如果面試官?zèng)]有指定解法我通常建議先用拓?fù)渑判蛩悸穪?lái)切入因?yàn)樗皖}目的“課程依賴”語(yǔ)義完美貼合。你可以先說(shuō)“這題本質(zhì)上是一個(gè)有向圖找環(huán)問(wèn)題我可以用拓?fù)渑判颉Ｏ冉y(tǒng)計(jì)每門課程的入度把入度為0的課程放入隊(duì)列然后不斷消除依賴。如果最后能處理完所有課程就說(shuō)明無(wú)環(huán)否則有環(huán)?！边@種回答幾乎不需要任何視覺(jué)化輔助面試官一聽(tīng)就知道你抓住了要害。寫完之后如果面試官追問(wèn)“你還能想到其他做法嗎”這時(shí)再補(bǔ)充DFS三色標(biāo)記并重點(diǎn)強(qiáng)調(diào)“單用visited不夠必須區(qū)分正在訪問(wèn)中和訪問(wèn)完”。這樣一主一備展示的深度會(huì)高不少。我也見(jiàn)過(guò)一部分候選人喜歡先講DFS因?yàn)樗麄儗?duì)遞歸更熟練。這沒(méi)問(wèn)題但要在動(dòng)筆前明確告訴面試官你的三色約定。否則面試官看到你代碼里出現(xiàn)0、1、2三個(gè)狀態(tài)還要逐一猜測(cè)溝通成本就上去了。4.3 從207到210的自然延伸面試官非常喜歡在寫完207之后加一句“如果我現(xiàn)在要求你不僅判斷能不能修完還要輸出一種合法修課順序你會(huì)怎么做”這道題就是LeetCode 210 Course Schedule II。如果剛才用的是Kahn解法擴(kuò)展幾乎是一行的事。把finished 1改成記錄彈出的課程res [] while q: course q.popleft() res.append(course) for nxt in adj[course]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return res if len(res) numCourses else []如果是DFS解法你也可以在遞歸回溯后把當(dāng)前節(jié)點(diǎn)記錄到棧中最后逆序輸出。但解釋起來(lái)比Kahn版本繞面試時(shí)容易說(shuō)得不夠清晰。這里可以考慮進(jìn)一步引申如果題目改成“返回所有可能的修課順序”復(fù)雜度就會(huì)變成指數(shù)級(jí)因?yàn)楹戏ㄍ負(fù)湫蚩赡芊浅６唷Ｃ嬖嚬偻ǔ２粫?huì)要求這么深但如果你主動(dòng)提一句邊界會(huì)顯得對(duì)問(wèn)題理解更完整。還有一個(gè)高頻追問(wèn)是“如果prerequisites里面有重復(fù)邊你的算法還能正確工作嗎”Kahn和DFS都能正確處理重復(fù)邊只是入度會(huì)多加幾次之后也會(huì)多減幾次最終計(jì)數(shù)正確不影響判斷。5. 常見(jiàn)錯(cuò)誤與排查技巧實(shí)錄5.1 錯(cuò)誤一鄰接表方向建反這道題最經(jīng)典的低級(jí)錯(cuò)誤就是把有向邊的方向搞反。比如寫成adj[cur].append(pre)那么所有“后繼”和“入度”的含義都會(huì)跟著顛倒。表面上看代碼結(jié)構(gòu)沒(méi)問(wèn)題但用手推一個(gè)最簡(jiǎn)單的用例就能暴露numCourses 2prerequisites [[1, 0]]正確情況下應(yīng)該0指向1錯(cuò)的情況下變成1指向0邏輯就全錯(cuò)了。排查方法是準(zhǔn)備一個(gè)最小可用用例手動(dòng)模擬一遍?？吹?是1的前置然后檢查自己的鄰接表到底存的是“前置指向后續(xù)”還是反過(guò)來(lái)。一旦方向明確后續(xù)DFS里的鄰居、Kahn里的入度全部自動(dòng)一致。5.2 錯(cuò)誤二只用visited布爾數(shù)組判環(huán)這是DFS解法里最容易出現(xiàn)的隱蔽錯(cuò)誤。如果只用一個(gè)布爾visited數(shù)組當(dāng)DFS回溯后再次遇到某個(gè)安全節(jié)點(diǎn)時(shí)由于visited已經(jīng)是True你可能會(huì)誤判為環(huán)。更麻煩的是有些寫法還會(huì)把“有環(huán)”漏掉因?yàn)榄h(huán)上的節(jié)點(diǎn)可能被提前標(biāo)記成已訪問(wèn)等遞歸回到環(huán)起點(diǎn)時(shí)判斷邏輯已經(jīng)亂了。務(wù)必向面試官解釋visited只能表示“這個(gè)節(jié)點(diǎn)之前到過(guò)”不能區(qū)分“正在遞歸棧中”和“已經(jīng)安全離開(kāi)”。后者才是環(huán)檢測(cè)的關(guān)鍵。使用三色狀態(tài)數(shù)組是這道題DFS解法最重要的細(xì)節(jié)。5.3 錯(cuò)誤三Kahn漏掉初始化隊(duì)列里的節(jié)點(diǎn)Kahn算法的初始化階段必須把所有入度為0的節(jié)點(diǎn)全部入隊(duì)。假設(shè)有100門課其中95門入度為0你只把其中5門放入隊(duì)列最終finished再多也不可能到100白白返回false。這種錯(cuò)誤在代碼審查時(shí)很隱蔽因?yàn)殡S著測(cè)試數(shù)據(jù)不同結(jié)果時(shí)好時(shí)壞。排查技巧很簡(jiǎn)單在入隊(duì)之后打印隊(duì)列長(zhǎng)度對(duì)比一下入度為0的節(jié)點(diǎn)數(shù)量再在while循環(huán)結(jié)束后打印finished。如果finished比預(yù)期的少先懷疑初始化是否漏了節(jié)點(diǎn)再看循環(huán)里是否有節(jié)點(diǎn)入度減到0但沒(méi)入隊(duì)。5.4 錯(cuò)誤四死循環(huán)或爆棧DFS版本如果狀態(tài)設(shè)計(jì)不當(dāng)遇到環(huán)時(shí)可能進(jìn)入無(wú)限遞歸最終以爆棧結(jié)束。Kahn版本如果忘記在遍歷鄰居時(shí)把入度減1或者減完忘了判斷是否為0同樣會(huì)陷入死循環(huán)或提前終止。這些錯(cuò)誤在你沒(méi)有針對(duì)環(huán)的用例進(jìn)行測(cè)試時(shí)非常難發(fā)現(xiàn)。我的習(xí)慣是用三個(gè)固定用例做自測(cè)最小無(wú)環(huán)用例[[1, 0]]應(yīng)該返回true最小環(huán)用例[[1, 0], [0, 1]]應(yīng)該返回false自環(huán)用例[[1, 1]]也要返回false。這三個(gè)用例如果都通過(guò)基本可以放心提交。5.5 調(diào)試心得可視化與打印刷算法題時(shí)本地調(diào)試有一個(gè)很有效的習(xí)慣把鄰接表和入度表打印出來(lái)看。比如print(adj) print(indegree)對(duì)DFS解法還可以在dfs入口加一行print(node, state)觀察遞歸路徑對(duì)Kahn解法可以在每輪循環(huán)后打印隊(duì)列和入度。一旦某個(gè)用例的結(jié)果不對(duì)通過(guò)打印內(nèi)容能迅速定位到是狀態(tài)標(biāo)記問(wèn)題、方向問(wèn)題還是隊(duì)列初始化問(wèn)題。很多錯(cuò)誤并不是算法思路錯(cuò)而是“數(shù)據(jù)結(jié)構(gòu)維護(hù)錯(cuò)”。把關(guān)鍵變量打印出來(lái)比自己盯著代碼反復(fù)猜要快得多。我個(gè)人在實(shí)際帶人做題時(shí)發(fā)現(xiàn)這道題最大的分水嶺不在會(huì)不會(huì)建圖而在能不能把“為什么三色標(biāo)記能判環(huán)”講到位。能講清楚的人說(shuō)明他對(duì)DFS遞歸棧、回溯、狀態(tài)生命周期都有真實(shí)理解。如果你能把Kahn解法寫穩(wěn)再把DFS三色作為備選講到讓對(duì)方點(diǎn)頭這道題基本就穩(wěn)了。最后再提一個(gè)小建議面試時(shí)不要急著一次把兩套代碼都寫完先把一套做到嚴(yán)謹(jǐn)無(wú)bug再用口述把另一套的思路表達(dá)清楚遠(yuǎn)比寫兩套半成品劃算得多。