如果有人正在準(zhǔn)備算法面試我建議一定不要跳過LeetCode 207這道Course Schedule。它是圖論里“有向圖找環(huán)”最標(biāo)準(zhǔn)的入門題也是一個(gè)非常經(jīng)典的“外表是課程表、內(nèi)核是圖模型”的面試題。題目會(huì)給你numCourses門課程以及一組先修關(guān)系prerequisites其中[a, b]表示要先修b才能修a問能不能把這些課程全部修完。把這組依賴關(guān)系看成一張有向圖問題瞬間就能翻譯成這張圖里是否存在環(huán)。存在環(huán)意味著課程互相依賴永遠(yuǎn)排不出合法順序不存在環(huán)所有課程才能逐步完成。這題最主流的兩種解法一種是DFS遞歸配合“三色標(biāo)記”另一種是拓?fù)渑判虻腒ahn算法迭代。這兩種解法我都建議不要只背模板而是徹底弄懂它們各自判定環(huán)的原理。下面我會(huì)從建模開始把兩條思路完整拆開再結(jié)合面試場(chǎng)景聊一聊怎么選擇、怎么避免翻車。1. 題目解讀從課程表到有向圖建模1.1 題目到底在問什么先看一個(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)。這種情況下哪門課都沒法“先修”所以答案是false。這類題目還有一個(gè)容易忽略的地方numCourses門課并不一定彼此關(guān)聯(lián)。有些課可能完全沒有任何先修關(guān)系有些課可能是其他課的“前置課程”但自己沒有任何前置。LeetCode這類題的測(cè)試用例里空依賴、孤立節(jié)點(diǎ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è)方向一旦定下來后面DFS和Kahn里的“鄰居”“入度”都要全部基于它來理解。如果方向建反了代碼可能不會(huì)立刻報(bào)錯(cuò)但邏輯會(huì)完全錯(cuò)位。在實(shí)際面試?yán)镂乙娺^太多人一開始沒想清楚寫完才發(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è)無環(huán)有向圖DAG一定存在至少一種拓?fù)渑判蚨灰獔D里有環(huán)環(huán)上的節(jié)點(diǎn)誰都無法先被滿足也就不存在合法順序。所以判定“能否完成全部課程”和判定“這張有向圖是否有環(huán)”是同一件事。這里還有一層值得向面試官說明的含義題目只要求判斷能否完成并不要求輸出具體的課程順序。所以你不需要真的排一個(gè)拓?fù)湫蛄兄灰袛唷澳懿荒芘拧?。這也是為什么DFS和Kahn都可以做到提前返回false而不必等全部遍歷結(jié)束。2. 解法一DFS遞歸 三色標(biāo)記2.1 核心思想把“訪問中”和“訪問完”分開很多人一看到判環(huán)第一反應(yīng)是維護(hù)一個(gè)布爾visited數(shù)組。但實(shí)際上只用visited非常容易誤判。原因在于DFS會(huì)回溯。某個(gè)節(jié)點(diǎn)可能先在一個(gè)分支里被訪問完之后另一個(gè)分支再路過它這屬于正常的復(fù)用并不代表出現(xiàn)環(huán)。真正需要抓的是在“當(dāng)前這次遞歸路徑”上是否又一次經(jīng)過了同一個(gè)節(jié)點(diǎn)。我習(xí)慣用三色狀態(tài)去解決0尚未訪問過1正在當(dāng)前遞歸路徑中也就是灰色狀態(tài)2已經(jīng)完整處理完且確認(rèn)這個(gè)節(jié)點(diǎn)所在的下游沒有環(huán)DFS遞歸時(shí)如果發(fā)現(xiàn)鄰居的狀態(tài)是1說明又繞回了當(dāng)前路徑上的某個(gè)節(jié)點(diǎn)這是環(huán)的直接證據(jù)如果發(fā)現(xiàn)狀態(tài)是2說明之前已經(jīng)驗(yàn)證過這顆子樹安全直接跳過即可。用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 未訪問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)過安全直接放行 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代碼看起來不長(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)最多訪問一次每條邊最多遍歷一次構(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 - ...遞歸深度可能直接超過限制拋出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í)遇到的反直覺坑三色標(biāo)記本身思路清晰但實(shí)現(xiàn)細(xì)節(jié)里容易踩坑。有一個(gè)非常常見的錯(cuò)誤是外層循環(huán)寫了range(numCourses)但dfs內(nèi)部偷懶只處理鄰接表非空的節(jié)點(diǎn)或者忽略孤立節(jié)點(diǎn)。這樣大部分用例能過但遇到一些特殊構(gòu)造就會(huì)出問題。比較穩(wěn)的做法是傳入任何節(jié)點(diǎn)都嚴(yán)格按照三色邏輯走一遍狀態(tài)為1返回False狀態(tài)為2返回True否則標(biāo)記1并遞歸。另一個(gè)反直覺的地方是自環(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)如果一門課程沒有任何先修課程它的入度就為0這門課現(xiàn)在就可以學(xué)。學(xué)完之后它會(huì)解除所有后續(xù)課程的一個(gè)依賴限制于是這些后續(xù)課程的入度各自減1。當(dāng)某個(gè)后續(xù)課程的入度減到0時(shí)說明它的所有前置課都已經(jīng)修完它也能進(jìn)入隊(duì)列。這個(gè)思路就像一層層“剝洋蔥”從沒有依賴的節(jié)點(diǎn)開始不斷移除“已經(jīng)可以完成的課”。最終如果所有課程都被移除說明圖無環(huán)如果隊(duì)列空了但還有課程沒有被移除說明剩下的節(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ì)忍不住只放“看起來和依賴關(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說明它所有前置課都完成了立刻加入隊(duì)列。最終只要看看finished是否等于numCourses即可。3.3 迭代解法的天然優(yōu)勢(shì)Kahn解法完全不用遞歸最直接的好處是不會(huì)遇到爆棧問題。Python跑長(zhǎng)鏈輸入時(shí)DFS可能還要擔(dān)心遞歸深度Kahn用一個(gè)隊(duì)列從頭走到尾穩(wěn)定性高很多。它對(duì)“正確性”的證明也更適合面試口述每一步都在模擬一個(gè)合法的選課過程入度為0的節(jié)點(diǎn)表示當(dāng)前沒有被未修完的前置課擋住彈出一個(gè)課程并解除它作為前置造成的影響是合理的。如果全部課程都能被彈出自然存在合法順序反之則說明剩下的節(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)遞歸上限沒有理解門檻需要對(duì)遞歸狀態(tài)有清晰認(rèn)識(shí)更貼近“依賴解除”的直覺擴(kuò)展到輸出課程順序需要額外記錄和逆序出隊(duì)順序就是合法順序面試急救價(jià)值展示圖論細(xì)節(jié)理解時(shí)加分穩(wěn)妥、快速、不易寫錯(cuò)4.2 面試時(shí)先說哪套更合適如果面試官?zèng)]有指定解法我通常建議先用拓?fù)渑判蛩悸穪砬腥胍驗(yàn)樗皖}目的“課程依賴”語(yǔ)義完美貼合。你可以先說“這題本質(zhì)上是一個(gè)有向圖找環(huán)問題我可以用拓?fù)渑判?。先統(tǒng)計(jì)每門課程的入度把入度為0的課程放入隊(duì)列然后不斷消除依賴。如果最后能處理完所有課程就說明無環(huán)否則有環(huán)?！边@種回答幾乎不需要任何視覺化輔助面試官一聽就知道你抓住了要害。寫完之后如果面試官追問“你還能想到其他做法嗎”這時(shí)再補(bǔ)充DFS三色標(biāo)記并重點(diǎn)強(qiáng)調(diào)“單用visited不夠必須區(qū)分正在訪問中和訪問完”。這樣一主一備展示的深度會(huì)高不少。我也見過一部分候選人喜歡先講DFS因?yàn)樗麄儗?duì)遞歸更熟練。這沒問題但要在動(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)記錄到棧中最后逆序輸出。但解釋起來比Kahn版本繞面試時(shí)容易說得不夠清晰。這里可以考慮進(jìn)一步引申如果題目改成“返回所有可能的修課順序”復(fù)雜度就會(huì)變成指數(shù)級(jí)因?yàn)楹戏ㄍ負(fù)湫蚩赡芊浅６?。面試官通常不?huì)要求這么深但如果你主動(dòng)提一句邊界會(huì)顯得對(duì)問題理解更完整。還有一個(gè)高頻追問是“如果prerequisites里面有重復(fù)邊你的算法還能正確工作嗎”Kahn和DFS都能正確處理重復(fù)邊只是入度會(huì)多加幾次之后也會(huì)多減幾次最終計(jì)數(shù)正確不影響判斷。5. 常見錯(cuò)誤與排查技巧實(shí)錄5.1 錯(cuò)誤一鄰接表方向建反這道題最經(jīng)典的低級(jí)錯(cuò)誤就是把有向邊的方向搞反。比如寫成adj[cur].append(pre)那么所有“后繼”和“入度”的含義都會(huì)跟著顛倒。表面上看代碼結(jié)構(gòu)沒問題但用手推一個(gè)最簡(jiǎn)單的用例就能暴露numCourses 2prerequisites [[1, 0]]正確情況下應(yīng)該0指向1錯(cuò)的情況下變成1指向0邏輯就全錯(cuò)了。排查方法是準(zhǔn)備一個(gè)最小可用用例手動(dòng)模擬一遍?？吹?是1的前置然后檢查自己的鄰接表到底存的是“前置指向后續(xù)”還是反過來。一旦方向明確后續(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)記成已訪問等遞歸回到環(huán)起點(diǎn)時(shí)判斷邏輯已經(jīng)亂了。務(wù)必向面試官解釋visited只能表示“這個(gè)節(jié)點(diǎn)之前到過”不能區(qū)分“正在遞歸棧中”和“已經(jīng)安全離開”。后者才是環(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但沒入隊(duì)。5.4 錯(cuò)誤四死循環(huán)或爆棧DFS版本如果狀態(tài)設(shè)計(jì)不當(dāng)遇到環(huán)時(shí)可能進(jìn)入無限遞歸最終以爆棧結(jié)束。Kahn版本如果忘記在遍歷鄰居時(shí)把入度減1或者減完忘了判斷是否為0同樣會(huì)陷入死循環(huán)或提前終止。這些錯(cuò)誤在你沒有針對(duì)環(huán)的用例進(jìn)行測(cè)試時(shí)非常難發(fā)現(xiàn)。我的習(xí)慣是用三個(gè)固定用例做自測(cè)最小無環(huán)用例[[1, 0]]應(yīng)該返回true最小環(huán)用例[[1, 0], [0, 1]]應(yīng)該返回false自環(huán)用例[[1, 1]]也要返回false。這三個(gè)用例如果都通過基本可以放心提交。5.5 調(diào)試心得可視化與打印刷算法題時(shí)本地調(diào)試有一個(gè)很有效的習(xí)慣把鄰接表和入度表打印出來看。比如print(adj) print(indegree)對(duì)DFS解法還可以在dfs入口加一行print(node, state)觀察遞歸路徑對(duì)Kahn解法可以在每輪循環(huán)后打印隊(duì)列和入度。一旦某個(gè)用例的結(jié)果不對(duì)通過打印內(nèi)容能迅速定位到是狀態(tài)標(biāo)記問題、方向問題還是隊(duì)列初始化問題。很多錯(cuò)誤并不是算法思路錯(cuò)而是“數(shù)據(jù)結(jié)構(gòu)維護(hù)錯(cuò)”。把關(guān)鍵變量打印出來比自己盯著代碼反復(fù)猜要快得多。我個(gè)人在實(shí)際帶人做題時(shí)發(fā)現(xiàn)這道題最大的分水嶺不在會(huì)不會(huì)建圖而在能不能把“為什么三色標(biāo)記能判環(huán)”講到位。能講清楚的人說明他對(duì)DFS遞歸棧、回溯、狀態(tài)生命周期都有真實(shí)理解。如果你能把Kahn解法寫穩(wěn)再把DFS三色作為備選講到讓對(duì)方點(diǎn)頭這道題基本就穩(wěn)了。最后再提一個(gè)小建議面試時(shí)不要急著一次把兩套代碼都寫完先把一套做到嚴(yán)謹(jǐn)無bug再用口述把另一套的思路表達(dá)清楚遠(yuǎn)比寫兩套半成品劃算得多。