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