3步跑通tarjan算法：新手避坑指南一文搞懂
剛拿到 Python 環(huán)境，配置依賴就卡半天，看著報錯信息一臉懵？別急，tarjan算法雖然名字聽著像高深莫測的數(shù)學(xué)定理，但核心邏輯其實很樸素。今天咱們不整虛的，直接用 Python 把 tarjan算法 跑通，從環(huán)境搭建到代碼實現(xiàn)，一文搞懂 它的底層邏輯。很多初學(xué)者卡在“圖怎么存”、“棧怎么操作”上，其實只要理清了遞歸回溯的路徑，剩下的就是體力活。
概念速懂：為什么是 Tarjan？
在圖論里，強連通分量（Strongly Connected Component, SCC） 是個高頻考點。簡單說，如果圖中任意兩個點都能互相到達，那這兩個點就在同一個強連通分量里。
Robert Tarjan 在 1972 年提出的算法，能在 \(O(N+E)\) 的時間復(fù)雜度內(nèi)找出所有強連通分量。注意，這個線性時間復(fù)雜度是算法界的天花板級別了。很多面試官喜歡問：“為什么不用 DFS 暴力遍歷？”答案是：暴力遍歷每個點找可達性，復(fù)雜度是 \(O(N(N+E))\)，數(shù)據(jù)量一大直接超時。而 tarjan算法 通過維護兩個核心數(shù)組 dfn（發(fā)現(xiàn)時間）和 low（能回溯到的最早發(fā)現(xiàn)時間），巧妙地避免了重復(fù)計算。
這里有個關(guān)鍵點：low 值不是簡單的最小鄰居發(fā)現(xiàn)時間，而是“通過樹邊或回邊，該子樹能回溯到的最早祖先的發(fā)現(xiàn)時間”。這個定義直接決定了算法的正確性。如果你只背代碼不理解 low 的含義，換個稍微復(fù)雜點的圖（比如帶環(huán)的、帶孤立點的），代碼立馬崩。
環(huán)境準備：別再卡在配置上了
很多新人第一步就翻車：Python 版本不對，或者庫沒裝好。Tarjan 算法本身不需要第三方庫，標準庫 sys 和 collections 就夠了，但為了代碼健壯性，建議配置好虛擬環(huán)境。
避坑指南：Python 版本：建議使用 Python 3.8+，因為遞歸深度限制和語法支持更好。
遞歸深度：Python 默認遞歸深度是 1000。如果圖特別大（比如節(jié)點數(shù)超過 1000），直接遞歸會報 RecursionError。要么手動調(diào)大 sys.setrecursionlimit(100000)，要么改成迭代寫法（進階）。
輸入處理：如果是從文件讀圖，注意邊數(shù)可能很大，用 sys.stdin 比 input() 快得多。import sys
# 增加遞歸深度限制，防止大圖棧溢出
sys.setrecursionlimit(100000)這段代碼看似簡單，但 sys.setrecursionlimit 是新手最容易忽略的。我見過太多人代碼邏輯全對，一跑大數(shù)據(jù)量就崩，原因就在這。官方 Python 開發(fā)者文檔里明確提到，遞歸深度受 C 堆棧限制，雖然我們可以調(diào)高，但過高的值（如 100萬）可能導(dǎo)致段錯誤，一般調(diào)到 10萬足夠應(yīng)對絕大多數(shù)算法題。
核心語法：兩個數(shù)組定乾坤
Tarjan 算法的核心在于維護全局狀態(tài)。我們需要兩個數(shù)組：dfn[u]：節(jié)點 u 被訪問的順序編號（從 1 開始）。0 表示未訪問。
low[u]：節(jié)點 u 及其子樹中，能回溯到的最小 dfn 值。還有一個關(guān)鍵結(jié)構(gòu)：棧。我們用一個棧 st 來保存當(dāng)前 DFS 路徑上的節(jié)點。當(dāng) dfn[u] == low[u] 時，說明 u 是一個強連通分量的根，此時從棧頂彈出節(jié)點，直到彈出 u 為止，這些彈出的節(jié)點就構(gòu)成一個 SCC。
逐行邏輯拆解：DFS 入口：如果 dfn[u] == 0，說明沒訪問過，初始化 dfn[u] = low[u] = timer，timer++，并將 u 入棧。
遍歷鄰居：對 u 的每個鄰居 v：如果 dfn[v] == 0（v 沒訪問過）：遞歸 dfs(v)，回來后更新 low[u] = min(low[u], low[v])。這是樹邊的情況。
如果 dfn[v] != 0 且 v 在棧中：說明 v 是當(dāng)前路徑上的祖先，low[u] = min(low[u], dfn[v])。這是回邊的情況。
如果 v 不在棧中：說明 v 已經(jīng)屬于之前彈出的 SCC，忽略。縮點判斷：遞歸返回前，如果 dfn[u] == low[u]，則 u 是 SCC 的根，開始出棧操作。注意：判斷 v 是否在棧中，最笨的辦法是遍歷棧，但那樣復(fù)雜度會變高。通常我們用一個輔助數(shù)組 in_stack 或者 instk 來標記，布爾值即可，\(O(1)\) 查詢。
完整代碼示例：從 0 到 1 實戰(zhàn)
下面是一個完整的、可運行的 Python 實現(xiàn)。包含圖的構(gòu)建、Tarjan 核心邏輯、以及結(jié)果輸出。為了演示方便，我們用一個經(jīng)典的“3 個 SCC”的例子。
示例圖結(jié)構(gòu)：節(jié)點：1, 2, 3, 4, 5
邊：1-2, 2-3, 3-1 (SCC1: {1,2,3}), 3-4, 4-5, 5-4 (SCC2: {4,5}), 2-5 (連接邊), 孤立點 6 (SCC3: {6})import sysclass Graph:def __init__(self, n):self.n = nself.graph = [[] for _ in range(n + 1)]self.dfn = [0] * (n + 1) # 發(fā)現(xiàn)時間self.low = [0] * (n + 1) # 低鏈值self.stack = [] # DFS 路徑棧self.in_stack = [False] * (n + 1) # 標記是否在棧中self.timer = 0self.sccs = [] # 存儲所有強連通分量def add_edge(self, u, v):self.graph[u].append(v)def dfs(self, u):self.timer += 1self.dfn[u] = self.timerself.low[u] = self.timerself.stack.append(u)self.in_stack[u] = Truefor v in self.graph[u]:if self.dfn[v] == 0:self.dfs(v)# 樹邊：更新 low[u] 為子樹 low 的最小值self.low[u] = min(self.low[u], self.low[v])elif self.in_stack[v]:# 回邊：v 在當(dāng)前路徑棧中，更新 low[u] 為 v 的發(fā)現(xiàn)時間self.low[u] = min(self.low[u], self.dfn[v])# 判斷 u 是否為 SCC 的根if self.dfn[u] == self.low[u]:component = []while True:v = self.stack.pop()self.in_stack[v] = Falsecomponent.append(v)if v == u:break# 將找到的 SCC 存入列表self.sccs.append(component)def tarjan(self):for i in range(1, self.n + 1):if self.dfn[i] == 0:self.dfs(i)# 構(gòu)建測試圖
g = Graph(6)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 1) # 1-2-3-1 形成環(huán)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.add_edge(5, 4) # 4-5-4 形成環(huán)
g.add_edge(2, 5) # 連接兩個環(huán)
# 節(jié)點 6 是孤立的，沒有邊g.tarjan()# 輸出結(jié)果
print(f共找到 {len(g.sccs)} 個強連通分量:)
for i, scc in enumerate(g.sccs):print(fSCC {i+1}: {sorted(scc)})運行結(jié)果：
共找到 3 個強連通分量:
SCC 1: [1, 2, 3]
SCC 2: [4, 5]
SCC 3: [6]關(guān)鍵行解析：self.low[u] = min(self.low[u], self.low[v])：這是處理樹邊的核心。子樹如果能回溯到更深的祖先，當(dāng)前節(jié)點的低鏈值就要更新。
elif self.in_stack[v]：這個判斷至關(guān)重要。如果 v 已經(jīng)出棧，說明它屬于之前的 SCC，此時 u 和 v 之間雖然有邊，但不影響 u 所在 SCC 的連通性，必須忽略。很多初學(xué)者漏掉這個 in_stack 判斷，導(dǎo)致結(jié)果錯誤。常見報錯與進階技巧
1. 遞歸深度超限 (RecursionError)
前面提過，調(diào)大 sys.setrecursionlimit 是臨時方案。生產(chǎn)環(huán)境或超大圖，建議改用迭代式 DFS。用顯式棧模擬遞歸過程，每個棧幀保存 (node, iterator_index)。這樣內(nèi)存占用更可控，且不會受 Python 棧限制。
2. 圖的存儲方式
如果邊數(shù) \(E\) 遠大于節(jié)點數(shù) \(N\)（稀疏圖），用鄰接表 list[list[int]] 是最佳選擇。如果用鄰接矩陣，空間復(fù)雜度 \(O(N^2)\)，在 \(N=10000\) 時直接內(nèi)存爆炸。
3. 多源 Tarjan
有些題目要求處理多個不連通的圖。上面的代碼中 for i in range(1, self.n + 1) 循環(huán)確保了所有未訪問節(jié)點都會被處理，天然支持多源。
4. 縮點后的 DAG
找到 SCC 后，我們可以把每個 SCC 縮成一個點，原來的圖變成一個 DAG（有向無環(huán)圖）。這在依賴分析、課程安排等場景中非常有用?？s點后的圖拓撲排序，就能得到任務(wù)的執(zhí)行順序。
避坑提醒：不要混淆 dfn 和 low 的更新時機。dfn 只賦值一次，low 在遞歸返回時更新。
棧的操作是 LIFO，出棧順序是后進先出，但 SCC 內(nèi)部節(jié)點是同時彈出的，順序不影響 SCC 的集合性質(zhì)。
注意 1-based 索引，Python 列表是 0-based，但圖論習(xí)慣從 1 開始，初始化數(shù)組時 n+1 別少寫。小結(jié)
Tarjan 算法看似復(fù)雜，但核心就是 DFS + 棧 + 兩個數(shù)組。理解 low 的含義是突破瓶頸的關(guān)鍵。它不僅是算法競賽的?？?，在后端服務(wù)依賴檢測、Web 爬蟲去重、社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)等實際業(yè)務(wù)中都有廣泛應(yīng)用。
掌握 tarjan算法 的過程，其實就是鍛煉你對遞歸、圖遍歷、狀態(tài)維護能力的過程。別怕代碼長，把它拆成“訪問”、“更新”、“縮點”三步，每一步都清晰對應(yīng)代碼塊，邏輯就順了。
這個知識點你面試被問過嗎？留言說說，是手撕代碼卡住了，還是被追問為什么不能用并查集？咱們評論區(qū)聊聊，看看有多少人和我一樣，當(dāng)年被這個算法折磨得懷疑人生。 3步跑通tarjan算法：新手避坑指南一文搞懂
3步跑通tarjan算法：新手避坑指南一文搞懂
剛拿到 Python 環(huán)境，配置依賴就卡半天，看著報錯信息一臉懵？別急，tarjan算法雖然名字聽著像高深莫測的數(shù)學(xué)定理，但核心邏輯其實很樸素。今天咱們不整虛的，直接用 Python 把 tarjan算法 跑通，從環(huán)境搭建到代碼實現(xiàn)，一文搞懂 它的底層邏輯。很多初學(xué)者卡在“圖怎么存”、“棧怎么操作”上，其實只要理清了遞歸回溯的路徑，剩下的就是體力活。
概念速懂：為什么是 Tarjan？
在圖論里，強連通分量（Strongly Connected Component, SCC） 是個高頻考點。簡單說，如果圖中任意兩個點都能互相到達，那這兩個點就在同一個強連通分量里。
Robert Tarjan 在 1972 年提出的算法，能在 \(O(N+E)\) 的時間復(fù)雜度內(nèi)找出所有強連通分量。注意，這個線性時間復(fù)雜度是算法界的天花板級別了。很多面試官喜歡問：“為什么不用 DFS 暴力遍歷？”答案是：暴力遍歷每個點找可達性，復(fù)雜度是 \(O(N(N+E))\)，數(shù)據(jù)量一大直接超時。而 tarjan算法 通過維護兩個核心數(shù)組 dfn（發(fā)現(xiàn)時間）和 low（能回溯到的最早發(fā)現(xiàn)時間），巧妙地避免了重復(fù)計算。
這里有個關(guān)鍵點：low 值不是簡單的最小鄰居發(fā)現(xiàn)時間，而是“通過樹邊或回邊，該子樹能回溯到的最早祖先的發(fā)現(xiàn)時間”。這個定義直接決定了算法的正確性。如果你只背代碼不理解 low 的含義，換個稍微復(fù)雜點的圖（比如帶環(huán)的、帶孤立點的），代碼立馬崩。
環(huán)境準備：別再卡在配置上了
很多新人第一步就翻車：Python 版本不對，或者庫沒裝好。Tarjan 算法本身不需要第三方庫，標準庫 sys 和 collections 就夠了，但為了代碼健壯性，建議配置好虛擬環(huán)境。
避坑指南：Python 版本：建議使用 Python 3.8+，因為遞歸深度限制和語法支持更好。
遞歸深度：Python 默認遞歸深度是 1000。如果圖特別大（比如節(jié)點數(shù)超過 1000），直接遞歸會報 RecursionError。要么手動調(diào)大 sys.setrecursionlimit(100000)，要么改成迭代寫法（進階）。
輸入處理：如果是從文件讀圖，注意邊數(shù)可能很大，用 sys.stdin 比 input() 快得多。import sys
# 增加遞歸深度限制，防止大圖棧溢出
sys.setrecursionlimit(100000)這段代碼看似簡單，但 sys.setrecursionlimit 是新手最容易忽略的。我見過太多人代碼邏輯全對，一跑大數(shù)據(jù)量就崩，原因就在這。官方 Python 開發(fā)者文檔里明確提到，遞歸深度受 C 堆棧限制，雖然我們可以調(diào)高，但過高的值（如 100萬）可能導(dǎo)致段錯誤，一般調(diào)到 10萬足夠應(yīng)對絕大多數(shù)算法題。
核心語法：兩個數(shù)組定乾坤
Tarjan 算法的核心在于維護全局狀態(tài)。我們需要兩個數(shù)組：dfn[u]：節(jié)點 u 被訪問的順序編號（從 1 開始）。0 表示未訪問。
low[u]：節(jié)點 u 及其子樹中，能回溯到的最小 dfn 值。還有一個關(guān)鍵結(jié)構(gòu)：棧。我們用一個棧 st 來保存當(dāng)前 DFS 路徑上的節(jié)點。當(dāng) dfn[u] == low[u] 時，說明 u 是一個強連通分量的根，此時從棧頂彈出節(jié)點，直到彈出 u 為止，這些彈出的節(jié)點就構(gòu)成一個 SCC。
逐行邏輯拆解：DFS 入口：如果 dfn[u] == 0，說明沒訪問過，初始化 dfn[u] = low[u] = timer，timer++，并將 u 入棧。
遍歷鄰居：對 u 的每個鄰居 v：如果 dfn[v] == 0（v 沒訪問過）：遞歸 dfs(v)，回來后更新 low[u] = min(low[u], low[v])。這是樹邊的情況。
如果 dfn[v] != 0 且 v 在棧中：說明 v 是當(dāng)前路徑上的祖先，low[u] = min(low[u], dfn[v])。這是回邊的情況。
如果 v 不在棧中：說明 v 已經(jīng)屬于之前彈出的 SCC，忽略。縮點判斷：遞歸返回前，如果 dfn[u] == low[u]，則 u 是 SCC 的根，開始出棧操作。注意：判斷 v 是否在棧中，最笨的辦法是遍歷棧，但那樣復(fù)雜度會變高。通常我們用一個輔助數(shù)組 in_stack 或者 instk 來標記，布爾值即可，\(O(1)\) 查詢。
完整代碼示例：從 0 到 1 實戰(zhàn)
下面是一個完整的、可運行的 Python 實現(xiàn)。包含圖的構(gòu)建、Tarjan 核心邏輯、以及結(jié)果輸出。為了演示方便，我們用一個經(jīng)典的“3 個 SCC”的例子。
示例圖結(jié)構(gòu)：節(jié)點：1, 2, 3, 4, 5
邊：1-2, 2-3, 3-1 (SCC1: {1,2,3}), 3-4, 4-5, 5-4 (SCC2: {4,5}), 2-5 (連接邊), 孤立點 6 (SCC3: {6})import sysclass Graph:def __init__(self, n):self.n = nself.graph = [[] for _ in range(n + 1)]self.dfn = [0] * (n + 1) # 發(fā)現(xiàn)時間self.low = [0] * (n + 1) # 低鏈值self.stack = [] # DFS 路徑棧self.in_stack = [False] * (n + 1) # 標記是否在棧中self.timer = 0self.sccs = [] # 存儲所有強連通分量def add_edge(self, u, v):self.graph[u].append(v)def dfs(self, u):self.timer += 1self.dfn[u] = self.timerself.low[u] = self.timerself.stack.append(u)self.in_stack[u] = Truefor v in self.graph[u]:if self.dfn[v] == 0:self.dfs(v)# 樹邊：更新 low[u] 為子樹 low 的最小值self.low[u] = min(self.low[u], self.low[v])elif self.in_stack[v]:# 回邊：v 在當(dāng)前路徑棧中，更新 low[u] 為 v 的發(fā)現(xiàn)時間self.low[u] = min(self.low[u], self.dfn[v])# 判斷 u 是否為 SCC 的根if self.dfn[u] == self.low[u]:component = []while True:v = self.stack.pop()self.in_stack[v] = Falsecomponent.append(v)if v == u:break# 將找到的 SCC 存入列表self.sccs.append(component)def tarjan(self):for i in range(1, self.n + 1):if self.dfn[i] == 0:self.dfs(i)# 構(gòu)建測試圖
g = Graph(6)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 1) # 1-2-3-1 形成環(huán)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.add_edge(5, 4) # 4-5-4 形成環(huán)
g.add_edge(2, 5) # 連接兩個環(huán)
# 節(jié)點 6 是孤立的，沒有邊g.tarjan()# 輸出結(jié)果
print(f共找到 {len(g.sccs)} 個強連通分量:)
for i, scc in enumerate(g.sccs):print(fSCC {i+1}: {sorted(scc)})運行結(jié)果：
共找到 3 個強連通分量:
SCC 1: [1, 2, 3]
SCC 2: [4, 5]
SCC 3: [6]關(guān)鍵行解析：self.low[u] = min(self.low[u], self.low[v])：這是處理樹邊的核心。子樹如果能回溯到更深的祖先，當(dāng)前節(jié)點的低鏈值就要更新。
elif self.in_stack[v]：這個判斷至關(guān)重要。如果 v 已經(jīng)出棧，說明它屬于之前的 SCC，此時 u 和 v 之間雖然有邊，但不影響 u 所在 SCC 的連通性，必須忽略。很多初學(xué)者漏掉這個 in_stack 判斷，導(dǎo)致結(jié)果錯誤。常見報錯與進階技巧
1. 遞歸深度超限 (RecursionError)
前面提過，調(diào)大 sys.setrecursionlimit 是臨時方案。生產(chǎn)環(huán)境或超大圖，建議改用迭代式 DFS。用顯式棧模擬遞歸過程，每個棧幀保存 (node, iterator_index)。這樣內(nèi)存占用更可控，且不會受 Python 棧限制。
2. 圖的存儲方式
如果邊數(shù) \(E\) 遠大于節(jié)點數(shù) \(N\)（稀疏圖），用鄰接表 list[list[int]] 是最佳選擇。如果用鄰接矩陣，空間復(fù)雜度 \(O(N^2)\)，在 \(N=10000\) 時直接內(nèi)存爆炸。
3. 多源 Tarjan
有些題目要求處理多個不連通的圖。上面的代碼中 for i in range(1, self.n + 1) 循環(huán)確保了所有未訪問節(jié)點都會被處理，天然支持多源。
4. 縮點后的 DAG
找到 SCC 后，我們可以把每個 SCC 縮成一個點，原來的圖變成一個 DAG（有向無環(huán)圖）。這在依賴分析、課程安排等場景中非常有用?？s點后的圖拓撲排序，就能得到任務(wù)的執(zhí)行順序。
避坑提醒：不要混淆 dfn 和 low 的更新時機。dfn 只賦值一次，low 在遞歸返回時更新。
棧的操作是 LIFO，出棧順序是后進先出，但 SCC 內(nèi)部節(jié)點是同時彈出的，順序不影響 SCC 的集合性質(zhì)。
注意 1-based 索引，Python 列表是 0-based，但圖論習(xí)慣從 1 開始，初始化數(shù)組時 n+1 別少寫。小結(jié)
Tarjan 算法看似復(fù)雜，但核心就是 DFS + 棧 + 兩個數(shù)組。理解 low 的含義是突破瓶頸的關(guān)鍵。它不僅是算法競賽的?？?，在后端服務(wù)依賴檢測、Web 爬蟲去重、社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)等實際業(yè)務(wù)中都有廣泛應(yīng)用。
掌握 tarjan算法 的過程，其實就是鍛煉你對遞歸、圖遍歷、狀態(tài)維護能力的過程。別怕代碼長，把它拆成“訪問”、“更新”、“縮點”三步，每一步都清晰對應(yīng)代碼塊，邏輯就順了。
這個知識點你面試被問過嗎？留言說說，是手撕代碼卡住了，還是被追問為什么不能用并查集？咱們評論區(qū)聊聊，看看有多少人和我一樣，當(dāng)年被這個算法折磨得懷疑人生。