强连通分量

强连通分量简介[编辑 | 编辑源代码]

强连通分量（Strongly Connected Component, SCC）是有向图中的一个极大子图，其中任意两个顶点互相可达（即存在双向路径）。形式化定义为：对于有向图 $G = (V, E)$ ，其强连通分量是顶点集 $C \subseteq V$ ，满足：

对任意 $u, v \in C$ ，存在 $u \to v$ 和 $v \to u$ 的路径。
不存在更大的集合 $C^{'} \supset C$ 满足上述条件。

关键性质[编辑 | 编辑源代码]

有向图的强连通分量构成其顶点的划分（即不重叠且覆盖全图）。
将每个 SCC 缩为一个顶点后，得到的是有向无环图（DAG）。

算法实现[编辑 | 编辑源代码]

常用算法包括 Kosaraju 算法和 Tarjan 算法。以下以 Kosaraju 算法为例：

Kosaraju 算法步骤[编辑 | 编辑源代码]

1. 第一次 DFS：对原图 $G$ 进行深度优先搜索，按完成时间逆序记录顶点。 2. 反转图：构造 $G$ 的转置图 $G^{T}$ （所有边反向）。 3. 第二次 DFS：按逆序在 $G^{T}$ 上 DFS，每棵树对应一个 SCC。

代码示例[编辑 | 编辑源代码]

from collections import defaultdict

def kosaraju(graph):
    visited = set()
    order = []
    
    # 第一次DFS生成逆序
    def dfs(u):
        stack = [(u, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                order.append(node)
                continue
            if node in visited:
                continue
            visited.add(node)
            stack.append((node, True))
            for v in graph[node]:
                if v not in visited:
                    stack.append((v, False))
    
    for u in graph:
        if u not in visited:
            dfs(u)
    
    # 构造转置图
    transposed = defaultdict(list)
    for u in graph:
        for v in graph[u]:
            transposed[v].append(u)
    
    # 第二次DFS找SCC
    visited.clear()
    sccs = []
    for u in reversed(order):
        if u not in visited:
            stack = [u]
            visited.add(u)
            component = []
            while stack:
                node = stack.pop()
                component.append(node)
                for v in transposed[node]:
                    if v not in visited:
                        visited.add(v)
                        stack.append(v)
            sccs.append(component)
    return sccs

# 示例输入
graph = {
    0: [1],
    1: [2],
    2: [0, 3],
    3: [4],
    4: [5],
    5: [3]
}
print(kosaraju(graph))  # 输出: [[0, 2, 1], [3, 5, 4]]