使用 Kosaraju 查找强连通分量
在原图上运行 DFS 获取完成顺序，转置图后按照完成顺序的逆序再次运行 DFS，以识别 SCC。
使用 Kosaraju 查找强连通分量 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
强连通分量定义
有向图中的强连通分量（SCC）是满足以下条件的极大节点集合：集合中的每个节点都存在一条路径可以到达集合中的其他任意节点。例如，如果节点 A、B、C 构成一个环（A→B→C→A），那么它们都属于同一个 SCC。没有自环的单个节点自身就是一个 SCC。SCC 可以揭示有向图的环结构。
Kosaraju 算法：两次 DFS 遍历
Kosaraju 算法使用两次 DFS 遍历，以 O(V + E) 的时间复杂度找出所有 SCC。第一次遍历：在原图上运行 DFS，并按节点的完成顺序（后序）将节点压入栈中。第二次遍历：在转置（反向）图上运行 DFS，按照完成顺序的逆序处理节点（从栈中弹出）。第二次遍历中的每棵 DFS 树就是一个 SCC。
Kosaraju 算法为何有效
在第一次遍历中，DFS 树最后完成的 SCC 没有指向其他 SCC 的出边（它是缩点 DAG 中的“汇”SCC）。在转置图中，该 SCC 没有来自其他 SCC 的入边，因此第二次遍历从它开始时，会始终停留在该 SCC 内。第二次遍历中的每次后续 DFS 也都会停留在各自的 SCC 内，因为所有跨 SCC 的边都已反向，并指向已经访问过的 SCC。
第一次遍历：构建完成顺序
在原图上运行 DFS，并在每个节点完成后（后序）将其压入栈中。第一次遍历不需要关注分量，只需记录完成顺序即可。最后完成的节点会位于缩点 DAG 的某个“源”SCC 中。
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graph第二次遍历：在转置图上运行 DFS
从完成顺序栈中弹出节点（优先处理完成时间最大的节点），并在转置图上运行 DFS。从未访问节点开始的每次 DFS 都会恰好发现一个 SCC。将这次 DFS 到达的所有节点标记为属于同一个分量。
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similar转置图
转置图会反转每条边：如果原图中有 u → v，转置图中就有 v → u。转置操作会保留 SCC——如果 A 和 B 在原图中属于同一个 SCC，那么它们在转置图中仍属于同一个 SCC（因为所有路径都反向了，但仍然保持连通）。如上所示，在解析输入时构建转置图，可以避免单独执行转置步骤。
大型图的迭代版本
对于大型图，请使用带显式栈的迭代 DFS 替代递归 DFS，以避免 Python 的递归限制。该迭代版本会压入节点、处理节点，并维护单独的“返回”标记来模拟后序遍历。
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')塔扬算法：SCC 的另一种方法
塔扬算法只需一次 DFS 遍历即可找出 SCC（而科萨拉朱算法需要两次遍历）。它会维护一个节点栈，并为每个节点分配一个发现时间和一个低链接值。当节点的发现时间等于其低链接值时，该节点就是一个 SCC 的根。塔扬算法的实现稍微复杂一些，但不需要构建转置图。两种算法的时间复杂度都是 O(V + E)。
SCC 的应用
SCC 可用于：(1) 编译器优化——识别相互递归的函数；(2) 社交网络分析——找出联系紧密的社群；(3) 2-SAT 问题——判断含两个文字的子句是否满足；(4) 网络爬取——识别具有大量交叉链接的页面集群；(5) 缩点 DAG——找到 SCC 后，图的缩点图是一个 DAG，因此可以对循环图进行拓扑分析。
缩点 DAG
有向图的缩点图会将每个 SCC 收缩为一个节点；如果两个 SCC 的组成节点之间存在边，就在对应的两个超节点之间添加一条边。结果始终是一个 DAG，因此可以在其上运行拓扑排序。这样一来，只适用于 DAG 的算法（例如 DP）也可以通过处理缩点图应用于一般的有向图。
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]SCC 的数量与图的性质
有向图中 SCC 的数量揭示了它的循环结构。DAG 有 n 个 SCC（每个节点都是自己的 SCC）。强连通图恰好有 1 个 SCC。一般来说，将 SCC 缩合后，它们会形成一个 DAG，即缩点图。如果缩点图中有唯一的源点（入度为 0 的节点）和唯一的汇点（出度为 0 的节点），则会满足某些连通性性质。这些性质会在添加最少边后判断可达性的问题中进行考查。
快速检查
检验您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中您学到了：SCC 是一组极大节点集合，其中每个节点都能从其他任一节点到达，科萨拉朱算法使用两次 DFS 遍历——第一次在原图上确定完成顺序，第二次在转置图上进行遍历，以及任何有向图的缩点图都是可用于进一步分析的 DAG。接下来，我们将构建用于 insert、search 和前缀操作的 TrieNode 数据结构。
常见问题解答
「使用 Kosaraju 查找强连通分量」课时是免费的吗？
是的 — 「使用 Kosaraju 查找强连通分量」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「使用 Kosaraju 查找强连通分量」这节课中我会学到什么？
在原图上运行 DFS 获取完成顺序，转置图后按照完成顺序的逆序再次运行 DFS，以识别 SCC。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「使用 Kosaraju 查找强连通分量」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- Kahn 算法：BFS 拓扑排序
- DFS 后序拓扑排序
- 课程表 I 与 II
- 使用 Kosaraju 查找强连通分量