1. 為什么一圈代碼會跑不完環(huán)檢測到底在解決什么問題1.1 先講一次把我整懵的“卡死”經(jīng)歷前陣子我接到一個排查任務(wù)線上服務(wù)時(shí)不時(shí)出現(xiàn)請求超時(shí)日志里沒有任何報(bào)錯只有某個接口的耗時(shí)曲線突然拉滿。翻代碼發(fā)現(xiàn)做權(quán)限校驗(yàn)時(shí)需要遞歸向上找“上級組織”有兩個組織節(jié)點(diǎn)被配成了互相指向?qū)Ψ?。這一遞歸進(jìn)去A找上級BB找上級A永遠(yuǎn)跳不出來直到線程池被耗盡。最后定位到原因時(shí)同事說了句大白話“這不就是循環(huán)了嘛?！蹦莻€瞬間我才意識到環(huán)Cycle這個問題在工程里出現(xiàn)的頻率遠(yuǎn)比想象中高依賴解析、任務(wù)編排、模塊加載、引用計(jì)數(shù)、狀態(tài)機(jī)遷移、死鎖檢測甚至正則表達(dá)式里的前向引用背后全是判環(huán)問題。Cycle Finding說直白點(diǎn)就是在一張圖里找出是否存在某個回路或者更進(jìn)一步把這條回路完整地挖出來。它不是一個只在算法書里出現(xiàn)的名詞而是很多線上故障的罪魁禍?zhǔn)住?.2 有向圖判環(huán)與無向圖判環(huán)壓根不是一回事很多人一開始容易犯的錯就是把“圖里有環(huán)”這件事想得太簡單。同樣是環(huán)在有向圖和無向圖里判定邏輯和算法選擇差異非常大。舉一個例子。無向圖里兩個節(jié)點(diǎn)之間只有一條邊三個節(jié)點(diǎn)兩兩相連就是三角形這在無向圖里是一個環(huán)。但在有向圖里如果邊是A指向B、B指向A這當(dāng)然算環(huán)而三條邊如果方向一致A→B→C→A也算環(huán)可如果方向不統(tǒng)一A→B→CC→A也可能構(gòu)成環(huán)。有向圖的環(huán)必須沿著邊的方向走能走回起點(diǎn)才算數(shù)所以判斷時(shí)要考慮方向性。無向圖的環(huán)則只要“連通性”上出現(xiàn)多余一條通路即可。這兩類問題的算法完全不同鏈表場景里經(jīng)典的做法是快慢指針也就是Floyd判圈算法有向圖里更常用的是DFS顏色標(biāo)記和拓?fù)渑判驘o向圖里則常用并查集和DFS。實(shí)際工程里你得先回答一個前置問題我要處理的圖是有向的還是無向的邊有沒有方向這個回答錯了后面所有算法都白搭。2. 烏龜和兔子Floyd判圈算法里最反直覺的那步2.1 快慢指針的物理直覺Floyd判圈算法是我最早接觸的Cycle Finding方案很多人也叫它“龜兔賽跑”。核心思路非常樸素用兩個指針同時(shí)從起點(diǎn)出發(fā)一個每次走一步另一個每次走兩步。如果鏈表中存在環(huán)那么快指針最終一定會“追上”慢指針并且兩者在環(huán)內(nèi)相遇如果沒有環(huán)快指針會先走到終點(diǎn)問題結(jié)束。為什么這樣能判環(huán)你可以想象兩個人在環(huán)形跑道上跑步速度快的人跑了兩圈之后和速度慢的人套圈相遇。鏈表里的“環(huán)”本質(zhì)上就是一條單向循環(huán)跑道快指針走兩步、慢指針走一步它們之間的相對速度是一步只要存在環(huán)它們的距離一定會逐步縮短到零也就是相遇。這個方案最值錢的地方在于只用兩個指針額外空間復(fù)雜度是O(1)不依賴哈希表去記錄訪問過的節(jié)點(diǎn)。2.2 找到環(huán)的入口為什么第一次相遇點(diǎn)藏著答案判定環(huán)是否存在只是第一步很多場景下我們還想知道環(huán)的入口在哪。Floyd算法里另一個著名結(jié)論是在快慢指針第一次相遇時(shí)把其中一個指針重置到鏈表頭部然后兩個指針都改成每次走一步它們再次相遇的位置就是環(huán)的入口。這個結(jié)論看起來神神叨叨但推導(dǎo)并不復(fù)雜。設(shè)鏈表頭到環(huán)入口的距離為a入口到第一次相遇點(diǎn)的距離為b相遇點(diǎn)到入口的剩余距離為c那么環(huán)周長就是bc。慢指針走了ab快指針走了ab k*(bc)其中k是快指針多繞的圈數(shù)。由于快指針?biāo)俣仁锹羔樀膬杀端杂衋bk*(bc) 2(ab)整理后得到 a k*(bc) - b。當(dāng)k1時(shí)a c。也就是說當(dāng)一個指針從頭部出發(fā)走a步到達(dá)環(huán)入口時(shí)另一個指針從相遇點(diǎn)出發(fā)走c步也能到達(dá)環(huán)入口因?yàn)橄嘤鳇c(diǎn)到環(huán)入口的距離恰好也是c。這就解釋了為什么“重置一個指針后同速走必然在入口碰到”。實(shí)際編碼的時(shí)候只需要注意邊界條件鏈表為空、只有一個節(jié)點(diǎn)、沒有環(huán)這三種情況都要單獨(dú)處理。我在某頭中圖的實(shí)現(xiàn)里踩過一次空指針就是因?yàn)橥伺袛鄁ast.next可能為null。def detect_cycle_entry(head): slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: break else: return None # 重置其中一個指針 slow head while slow ! fast: slow slow.next fast fast.next return slow2.3 使用范圍與邊界Floyd算法不是萬能的Floyd算法的適用場景非常明確線性結(jié)構(gòu)可能存在尾部環(huán)典型就是單鏈表、迭代器的循環(huán)序列。但如果你面對的是一個真正的“圖”比如節(jié)點(diǎn)有多條出邊Floyd就完全不適用了。因?yàn)榭炻羔樢蕾嚨氖且粭l確定的“走下去”的路徑而圖結(jié)構(gòu)里同一個節(jié)點(diǎn)出發(fā)可能同時(shí)有多個選擇你無法定義“下一個節(jié)點(diǎn)”是誰。還有一個容易忽略的點(diǎn)Floyd只能判斷有沒有環(huán)和找到入口如果要輸出完整的環(huán)路徑它就不夠用了。鏈表場景里你可以從入口沿著走一圈但圖的場景下還是得依賴DFS和路徑記錄。所以我現(xiàn)在的判斷標(biāo)準(zhǔn)是遇到鏈表或單路徑迭代問題優(yōu)先想到Floyd遇到多分支的圖直接換算法別再硬套。3. 有向圖上的通用判環(huán)DFS三色標(biāo)記和Kahn拓?fù)渑判?.1 三色標(biāo)記從遞歸棧里找回兜底有向圖判環(huán)最直觀的解法是DFS。但普通的DFS加一個visited布爾數(shù)組是不夠的因?yàn)槟憧赡茉跓o環(huán)的情況下重復(fù)訪問一個節(jié)點(diǎn)誤判成環(huán)。經(jīng)典的解決方案是給每個節(jié)點(diǎn)引入三種狀態(tài)0白色未訪問1灰色正在當(dāng)前遞歸棧中訪問2黑色訪問完成確認(rèn)無環(huán)核心邏輯是DFS遍歷時(shí)如果遇到一個灰色節(jié)點(diǎn)說明從當(dāng)前節(jié)點(diǎn)出發(fā)有一條路徑能走回它自己這就是環(huán)。如果是白色節(jié)點(diǎn)則正常遞歸如果是黑色節(jié)點(diǎn)直接跳過因?yàn)橐呀?jīng)處理過了。這個“灰色”狀態(tài)其實(shí)就是遞歸調(diào)用鏈路的記錄相當(dāng)于把系統(tǒng)棧顯式地搬到了狀態(tài)數(shù)組里。我見過不少初學(xué)者只用一個布爾visited結(jié)果在無環(huán)的有向圖里也會誤判成有環(huán)問題就出在沒辦法區(qū)分“已經(jīng)處理完的節(jié)點(diǎn)”和“正在處理鏈路上的節(jié)點(diǎn)”。三色標(biāo)記花不了多少代碼量卻能避免這種經(jīng)典的邏輯漏洞。WHITE, GRAY, BLACK 0, 1, 2 def has_cycle(graph): state {node: WHITE for node in graph} def dfs(node): if state[node] GRAY: return True if state[node] BLACK: return False state[node] GRAY for neighbor in graph[node]: if dfs(neighbor): return True state[node] BLACK return False for node in graph: if state[node] WHITE: if dfs(node): return True return False這套實(shí)現(xiàn)的復(fù)雜度是O(VE)空間復(fù)雜度是O(V)因?yàn)橐~外存狀態(tài)。在節(jié)點(diǎn)數(shù)量很大的時(shí)候遞歸深度可能不夠用需要改成顯式棧。我自己在某項(xiàng)目里處理過幾萬個節(jié)點(diǎn)的配置依賴圖Python默認(rèn)遞歸深度根本扛不住后來改成了迭代式DFS。3.2 Kahn算法依賴入度為0的節(jié)點(diǎn)不斷剝離如果要判有向圖是否有環(huán)還有一條更“工程化”的路拓?fù)渑判?。Kahn算法的思路特別務(wù)實(shí)一個無環(huán)有向圖一定能找到一個入度為0的節(jié)點(diǎn)把它拿掉之后剩下的圖仍然是無環(huán)的于是可以持續(xù)剝離直到所有節(jié)點(diǎn)都被處理。反過來如果存在環(huán)環(huán)內(nèi)所有節(jié)點(diǎn)的入度永遠(yuǎn)至少為1永遠(yuǎn)無法被剝離所以最終會剩下節(jié)點(diǎn)處理不完。算法步驟非常直接統(tǒng)計(jì)每個節(jié)點(diǎn)的入度。把所有入度為0的節(jié)點(diǎn)放進(jìn)隊(duì)列。依次彈出隊(duì)列節(jié)點(diǎn)把它的所有出邊去掉對應(yīng)鄰居入度減一。如果鄰居入度變?yōu)?繼續(xù)入隊(duì)。處理完隊(duì)列后檢查已處理節(jié)點(diǎn)數(shù)量如果小于總節(jié)點(diǎn)數(shù)說明有環(huán)。Kahn算法的優(yōu)勢在于它不只是告訴你有沒有環(huán)還會順帶給你一個合法的拓?fù)湫蛄小＿@在依賴解析、構(gòu)建順序、任務(wù)編排這類場景里特別有意義——你不但要知道依賴關(guān)系對不對還需要一個可執(zhí)行順序。如果發(fā)現(xiàn)有環(huán)剩下的未處理節(jié)點(diǎn)集合往往就近似環(huán)的成員能幫你縮小排查范圍。from collections import deque def has_cycle_kahn(graph): indegree {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] indegree.get(neighbor, 0) 1 queue deque([node for node in graph if indegree[node] 0]) visited_count 0 while queue: node queue.popleft() visited_count 1 for neighbor in graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) return visited_count ! len(graph)細(xì)心的人會問那如果我用DFS三色標(biāo)記已經(jīng)能判環(huán)了為什么還要學(xué)Kahn?因?yàn)閮烧叩男畔⒘坑胁顒e。DFS三色標(biāo)記更擅長“快速回答是或否”Kahn更擅長“告訴你可以怎么安排順序”。在一個超大依賴圖的場景里二者往往配合使用先用Kahn做拓?fù)渑判蚺挪粍恿嗽儆肈FS找出具體的環(huán)成員。3.3 兩種方法該選誰取決于你要的答案形態(tài)我自己的選擇標(biāo)準(zhǔn)大概是這樣的需求場景推薦方案原因只需要判斷有沒有環(huán)DFS三色標(biāo)記代碼簡單遞歸或迭代都能實(shí)現(xiàn)遍歷過程中能順便記錄路徑需要輸出完整環(huán)路徑DFS三色標(biāo)記路徑棧遞歸過程中能記錄當(dāng)前鏈路遇到灰節(jié)點(diǎn)時(shí)鏈路就是環(huán)需要合法的處理順序Kahn拓?fù)渑判蛑苯赢a(chǎn)出拓?fù)湫蜻€能識別哪些節(jié)點(diǎn)像環(huán)成員圖特別大遞歸不好寫Kahn或迭代式DFS避免系統(tǒng)棧溢出還能靈活控制內(nèi)存注意這里的“圖特別大”要看實(shí)際規(guī)模。幾十萬節(jié)點(diǎn)的圖DFS三色標(biāo)記依然很快但千萬級以上的圖Kahn因?yàn)橛昧岁?duì)列可以用增量方式處理配合外部存儲做分批加載工程上更好落地。4. 無向圖判環(huán)并查集這個被低估的思路4.1 并查集與“邊兩端已連通 → 有環(huán)”的核心推理無向圖的判環(huán)很多人第一反應(yīng)還是DFS但工程上我強(qiáng)烈推薦并查集。它的核心推理只有一句話在逐步加邊的過程中如果一條邊的兩個端點(diǎn)已經(jīng)屬于同一個連通集合那這條邊加進(jìn)來必然形成一個環(huán)。為什么想象一下無向圖里的環(huán)本質(zhì)上就是一條邊把兩個本來已經(jīng)通過其他路徑連通的點(diǎn)再次連接起來。比如三個點(diǎn)A、B、C原來有A-B、B-C兩條邊這時(shí)候A和C已經(jīng)連通了如果再來一條A-C的邊那A-C和A-B-C就構(gòu)成了一個環(huán)。并查集做的事情就是維護(hù)這種“連通性”關(guān)系。實(shí)現(xiàn)上并查集有兩大優(yōu)化路徑壓縮和按秩合并。路徑壓縮讓每個節(jié)點(diǎn)直接指向根節(jié)點(diǎn)后續(xù)查找?guī)缀跏荗(1)按秩合并則保證樹的深度始終較小。兩者配合整個算法的攤還復(fù)雜度接近O(1)處理百萬級邊也無壓力。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 return True def has_cycle_undirected(n, edges): dsu DSU(n) for u, v in edges: if not dsu.union(u, v): return True return False4.2 對自環(huán)、重邊、大圖壓縮的實(shí)操處理并查集雖然好用但工程上會有一堆邊界情況。我自己踩過幾個坑寫出來供大家避雷。第一個是自環(huán)。一個點(diǎn)自己指向自己在無向圖里算環(huán)。但在并查集里union(x, x)執(zhí)行時(shí)會發(fā)現(xiàn)find(parent_x) parent_x直接返回False判定有環(huán)。這個行為是正確的但如果你懶省事用鄰接矩陣或者只檢查重邊就漏了。第二個是重邊。兩條完全相同的邊比如A-B出現(xiàn)兩次第一次加上時(shí)A和B連通第二次再加時(shí)find結(jié)果相同于是判定有環(huán)。這個邏輯也沒問題但要注意題意有些業(yè)務(wù)場景里“兩條相同邊”不該算環(huán)比如網(wǎng)絡(luò)拓?fù)渲袃蓚€節(jié)點(diǎn)之間有多條物理鏈路。這時(shí)候就得先對邊去重再做判環(huán)。第三個是大圖的內(nèi)存。如果節(jié)點(diǎn)是稀疏的可以用字典來存儲parent而不是數(shù)組。我在某項(xiàng)目里處理的是字符串ID而不是序號直接開數(shù)組就傻眼了后來改成字典版并查集代碼量差不多但靈活很多。4.3 有向圖和無向圖判環(huán)的方法對比我整理了一張對照表方便大家用到時(shí)直接查對比維度有向圖無向圖核心算法DFS三色標(biāo)記、Kahn拓?fù)渑判駾FS、并查集時(shí)間復(fù)雜度O(VE)并查集接近O(1)均攤典型場景依賴解析、編譯順序、死鎖檢測網(wǎng)絡(luò)連通性、最小生成樹、地圖圍欄邊界細(xì)節(jié)同一條邊方向相反也算環(huán)自環(huán)和重邊要按業(yè)務(wù)定義處理能否輸出環(huán)路徑三色標(biāo)記可以Kahn不行并查集不行需要另存邊再回溯特別強(qiáng)調(diào)一點(diǎn)不要把有向圖的DFS三色標(biāo)記直接搬到無向圖上。無向圖里沒有“方向”的概念DFS時(shí)你從一個節(jié)點(diǎn)出發(fā)遇到已訪問過的鄰居很可能只是因?yàn)樗悄銊倎淼哪莻€節(jié)點(diǎn)也就是回邊。不做“跳過父節(jié)點(diǎn)”的處理任何一個無環(huán)的無向圖都能讓你誤報(bào)有環(huán)。5. 工程上的坑輸出環(huán)路徑、流式數(shù)據(jù)與超大數(shù)據(jù)量5.1 輸出環(huán)路徑不只是判斷“有沒有”很多業(yè)務(wù)場景下判環(huán)只是第一步產(chǎn)品經(jīng)理緊接著就會問環(huán)是誰和誰組成的你得把環(huán)路徑完整地打印出來才能定位到具體是哪些配置寫錯了。在有向圖里用DFS三色標(biāo)記可以順便輸出環(huán)路徑。做法是在進(jìn)入遞歸時(shí)維護(hù)一個路徑棧節(jié)點(diǎn)入棧時(shí)標(biāo)記為灰色出棧時(shí)恢復(fù)為白色或標(biāo)記為黑色。如果發(fā)現(xiàn)某個鄰居已經(jīng)是灰色那么從棧里找到該鄰居的位置從那個位置到棧頂?shù)乃泄?jié)點(diǎn)就是一條完整環(huán)路徑。這里有個容易出錯的地方遞歸函數(shù)里路徑棧的入棧和出棧必須配對。我見過有同事在return True之前忘了把當(dāng)前節(jié)點(diǎn)彈棧導(dǎo)致輸出了一大段不相關(guān)的路徑。更穩(wěn)妥的做法是在遞歸返回后再統(tǒng)一彈棧保證每個節(jié)點(diǎn)的入棧和出棧嚴(yán)格對稱?；氐綗o向圖的并查集它本身不維護(hù)路徑信息所以如果要輸出環(huán)路徑就得在并查集之外另存一份鄰接表判到環(huán)時(shí)再用DFS或BFS把路徑挖出來。這會增加額外復(fù)雜度但如果業(yè)務(wù)確實(shí)需要也別怕先想清楚流程再動手。5.2 在線/流式場景下的環(huán)檢測還有一種讓人頭疼的場景是數(shù)據(jù)源源不斷進(jìn)來圖是在線增長的。比如用戶動態(tài)加好友、任務(wù)動態(tài)插入新依賴你不能每次都重建整張圖重新判環(huán)那樣大圖根本扛不住。增量判環(huán)沒有銀彈。如果是無向圖并查集天然支持在線判定加一條邊就合并一次如果union失敗就說明剛加的這條邊產(chǎn)生了環(huán)復(fù)雜度穩(wěn)定。如果是有向圖增量判環(huán)就麻煩得多新加一條邊u→v可能產(chǎn)生環(huán)當(dāng)且僅當(dāng)v已經(jīng)可以通過某些路徑到達(dá)u也就是需要做一次從v出發(fā)的可達(dá)性查詢。這個查詢快則O(VE)慢則更糟屬于沒有特別好辦法的問題。我的實(shí)踐經(jīng)驗(yàn)是如果實(shí)在繞不開大圖的增量回溯可以考慮折中方案——定期批量重建。既然每次查詢都做全圖DFS成本太高那就在一個批次內(nèi)只做局部DFS控制遍歷深度超出閾值則標(biāo)記為“待重查”這樣能兼顧實(shí)時(shí)性和性能。5.3 大規(guī)模圖處理的兜底策略最后聊一下數(shù)據(jù)規(guī)模非常大時(shí)的處理。圖數(shù)據(jù)放不進(jìn)內(nèi)存怎么辦兩個思路。第一個是分區(qū)判環(huán)。把圖按強(qiáng)連通分量或連通塊劃分分塊內(nèi)判環(huán)、塊間判環(huán)分開處理。注意強(qiáng)連通分量本身是環(huán)檢測的天然聚合一個強(qiáng)連通分量要么是單點(diǎn)要么包含至少一個環(huán)。所以有向圖判環(huán)也可以先縮點(diǎn)再看縮點(diǎn)后的DAG是否有環(huán)。第二個是外存判環(huán)。用數(shù)據(jù)庫或文件存儲圖的邊關(guān)系按批次加載到內(nèi)存做部分處理Kahn算法天然適合這種分批方式先把能處理的入度為零的節(jié)點(diǎn)連續(xù)處理掉留下來的節(jié)點(diǎn)肯定屬于某個環(huán)。每處理一批就重新統(tǒng)計(jì)一次入度雖然IO開銷大了些但能處理遠(yuǎn)超內(nèi)存的數(shù)據(jù)量。還有一個小經(jīng)驗(yàn)在超大規(guī)模圖里不要頻繁使用遞歸盡量用迭代。并不是每次都會棧溢出但幾十萬層的遞歸在大多數(shù)運(yùn)行時(shí)環(huán)境里都不太穩(wěn)妥。交替使用隊(duì)列和棧把顯式的訪問狀態(tài)用數(shù)組管理起來性能穩(wěn)定得多。6. 回到開頭那個真實(shí)案例我是怎么定位和修復(fù)的6.1 從日志到依賴圖的層層排查回到文章開頭提到的線上卡死問題。我當(dāng)時(shí)第一反應(yīng)是檢查是不是代碼里有死循環(huán)人肉讀代碼沒找到明顯問題。后來把請求鏈路打出來發(fā)現(xiàn)每次都經(jīng)過同樣兩個節(jié)點(diǎn)才意識到可能是組織關(guān)系配置成了環(huán)。我做了個簡單的模擬把組織上下級關(guān)系抽成有向圖節(jié)點(diǎn)是組織ID邊是“上級指向”。跑了一遍Kahn算法很快確認(rèn)存在環(huán)然后用DFS三色標(biāo)記挖出了那條環(huán)路徑A→B→A。定位到具體那兩個組織后修復(fù)就很直接了——調(diào)整錯誤配置讓鏈路變成樹狀結(jié)構(gòu)。6.2 修復(fù)后的防御入口校驗(yàn) 定期巡檢修復(fù)一次不算完重點(diǎn)是防止再次發(fā)生。我后來在配置保存接口里加了一層校驗(yàn)每次修改組織關(guān)系時(shí)先對整張圖做一次Kahn判環(huán)不通過就拒絕保存。同時(shí)在數(shù)據(jù)入庫之前用并查集和DFS雙重校驗(yàn)保證無論如何都不會出現(xiàn)環(huán)配置。這套做法上線之后同類問題再也沒有復(fù)現(xiàn)過。從中我得到一個經(jīng)驗(yàn)環(huán)檢測這類工具最理想的位置不是等到問題爆發(fā)再去排查而是寫在數(shù)據(jù)輸入的邊界上。寧可每次多花幾百毫秒做校驗(yàn)也別讓一條壞數(shù)據(jù)流到線上導(dǎo)致整點(diǎn)級別的故障。6.3 個人體會判環(huán)題目刷再多不如跑到真實(shí)業(yè)務(wù)里一次坦白說Cycle Finding在算法題里屬于入門偏上的難度Floyd、三色標(biāo)記、拓?fù)渑判颉⒉⒉榧總€都有對應(yīng)的模板題。但真正讓我覺得“會了”的時(shí)刻不是背下代碼而是面對一個真實(shí)故障時(shí)能在五分鐘內(nèi)判斷出該用哪一種算法、該怎么改造成生產(chǎn)級的代碼。如果讓我給一個學(xué)習(xí)路徑上的建議先把無向圖的并查集和有向圖的Kahn寫熟這兩個代碼量少、邏輯直接、面試和工程里出鏡率最高然后補(bǔ)DFS三色標(biāo)記因?yàn)樗俏ㄒ荒茼樖州敵鐾暾h(huán)路徑的方案最后再啃Floyd把它當(dāng)成一個“鏈表專屬的優(yōu)化技巧”來學(xué)。反過來學(xué)也沒問題但別把Floyd誤當(dāng)成全圖判環(huán)的通用解法。真正處理過的圖一多你會發(fā)現(xiàn)環(huán)檢測從來不是一個孤立的算法題它是圖論思維在工程世界里的縮影。判斷出環(huán)的位置找到環(huán)的成因阻止環(huán)的產(chǎn)生這套思路比任何單段代碼都值錢。