图的连通性判断Tarjan 与 Kosaraju 的实现细节与复杂度对比一、两种算法都能求 SCC区别在哪强连通分量SCC是图论中的核心概念。Tarjan 和 Kosaraju 是求 SCC 的两种经典算法复杂度和都是 O(VE)。但如果选型只看复杂度就很难区分它们。这篇文章从实现细节、运行特征和适用场景三个维度对比这两个算法。二、算法流程对比flowchart LR subgraph Tarjan T1[一次 DFS] -- T2[维护 dfn 和 low] T2 -- T3[low u dfn u 时弹出 SCC] end subgraph Kosaraju K1[第一次 DFS] -- K2[记录出栈顺序] K2 -- K3[反转图] K3 -- K4[第二次 DFS 按出栈逆序] K4 -- K5[每次 DFS 得出一个 SCC] end三、实现对比from typing import List class TarjanSCC: Tarjan 算法求强连通分量 核心思想在一次 DFS 中同时完成遍历和 SCC 识别。 利用 dfn发现时间和 low能回溯到的最早节点来判断 当前节点是否为 SCC 的根。 时间复杂度O(V E)只需一次 DFS 空间复杂度O(V)需要栈 dfn/low 数组 def __init__(self, n: int): self.n n self.graph: list[list[int]] [[] for _ in range(n)] # 算法辅助结构 self.dfn [0] * n # 节点发现时间0 表示未访问 self.low [0] * n # 节点能回溯到的最早 dfn self.in_stack [False] * n self.stack [] self.time 0 self.sccs [] # 存储所有 SCC def add_edge(self, u: int, v: int) - None: self.graph[u].append(v) def find_sccs(self) - List[List[int]]: 查找所有强连通分量 for i in range(self.n): if self.dfn[i] 0: self._dfs(i) return self.sccs def _dfs(self, u: int) - None: 核心 DFS self.time 1 self.dfn[u] self.low[u] self.time self.stack.append(u) self.in_stack[u] True # 遍历邻接节点 for v in self.graph[u]: if self.dfn[v] 0: # 树边v 未被访问过继续 DFS self._dfs(v) # 回溯时更新 low子节点能到的最早节点父节点也能到 self.low[u] min(self.low[u], self.low[v]) elif self.in_stack[v]: # 回边v 在栈中说明 u 可以通过回边到达 v # 注意这里用 dfn[v] 而非 low[v] # 因为 v 的 low 可能还未完全确定 self.low[u] min(self.low[u], self.dfn[v]) # 如果 u 是 SCC 的根节点low[u] dfn[u] if self.low[u] self.dfn[u]: scc [] while True: v self.stack.pop() self.in_stack[v] False scc.append(v) if v u: break self.sccs.append(scc) class KosarajuSCC: Kosaraju 算法求强连通分量 核心思想两次 DFS。 第一次 DFS 记录节点出栈顺序后序遍历。 第二次 DFS 在反向图上按出栈逆序访问 每次 DFS 访问到的节点构成一个 SCC。 时间复杂度O(V E)需要两次 DFS 空间复杂度O(V E)需要存储反向图 def __init__(self, n: int): self.n n self.graph: list[list[int]] [[] for _ in range(n)] self.reverse_graph: list[list[int]] [[] for _ in range(n)] self.visited [False] * n def add_edge(self, u: int, v: int) - None: self.graph[u].append(v) self.reverse_graph[v].append(u) # 同时维护反向图 def find_sccs(self) - List[List[int]]: 查找所有强连通分量 # 第一次 DFS记录出栈顺序 order [] self.visited [False] * self.n for i in range(self.n): if not self.visited[i]: self._dfs1(i, order) # 第二次 DFS在反向图上按出栈逆序访问 self.visited [False] * self.n sccs [] for u in reversed(order): # 关键按出栈逆序 if not self.visited[u]: scc [] self._dfs2(u, scc) sccs.append(scc) return sccs def _dfs1(self, u: int, order: list) - None: 第一次 DFS在正向图上记录出栈顺序 self.visited[u] True for v in self.graph[u]: if not self.visited[v]: self._dfs1(v, order) order.append(u) # 后序遍历访问完所有子节点后记录 def _dfs2(self, u: int, scc: list) - None: 第二次 DFS在反向图上收集 SCC self.visited[u] True scc.append(u) for v in self.reverse_graph[u]: if not self.visited[v]: self._dfs2(v, scc)四、核心差异与选型维度TarjanKosarajuDFS 次数1 次2 次额外空间O(V)栈 dfn/lowO(VE)反向图实现难度中等需要理解 low/dfn简单两次标准 DFS运行时特征一次 DFS 完成两次 DFS图需要反转递归深度风险一样一样动态添加边不方便需重建所有状态不方便需重建反向图Tarjan 的优势单次 DFS常数因子更优不需要额外存储反向图Kosaraju 的优势概念简单两次标准 DFS没有 dfn/low 的复杂状态代码更易懂调试方便两次 DFS 的逻辑完全独立可以并行化什么时候用哪个面试/教学Kosaraju因为更容易讲清楚正确性。竞赛/对常数敏感Tarjan单次 DFS 常数更小。需要动态更新 SCC两者都不适合应该用动态图的 SCC 维护算法。五、总结Tarjan 和 Kosaraju 的理论复杂度相同但工程选择不同。Tarjan 胜在常数更小Kosaraju 胜在思路更直观。在很多实际场景中Kosaraju 的实现简单性带来的维护优势可能超过 Tarjan 的微小性能优势。选型时考虑的是「谁更好维护和调试」而不仅是「谁的理论常数更小」。