编辑“︁强连通分量”︁

{{Note|本文介绍图论中的'''强连通分量'''（Strongly Connected Components, SCC）概念及其算法实现，适合初学者逐步理解。}}

== 强连通分量简介 ==
'''强连通分量'''（Strongly Connected Component, SCC）是[[有向图]]中的一个极大子图，其中任意两个顶点互相可达（即存在双向路径）。形式化定义为：对于有向图 <math>G=(V,E)</math>，其强连通分量是顶点集 <math>C \subseteq V</math>，满足：
* 对任意 <math>u,v \in C</math>，存在 <math>u \rightarrow v</math> 和 <math>v \rightarrow u</math> 的路径。
* 不存在更大的集合 <math>C' \supset C</math> 满足上述条件。

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

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

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

=== 代码示例 ===
<syntaxhighlight lang="python">
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]]
</syntaxhighlight>

=== 输入输出说明 ===
* 输入：有向图的邻接表表示。
* 输出：强连通分量列表，每个分量是顶点的集合。示例中 SCC 为 <math>\{0,1,2\}</math> 和 <math>\{3,4,5\}</math>。

== 可视化示例 ==
<mermaid>
graph LR
    0 --> 1
    1 --> 2
    2 --> 0
    2 --> 3
    3 --> 4
    4 --> 5
    5 --> 3
</mermaid>
* SCC 1: 0 ↔ 1 ↔ 2  
* SCC 2: 3 ↔ 4 ↔ 5  

== 实际应用 ==
1. '''编译器优化'''：检测代码中的循环依赖（如函数调用图）。
2. '''社交网络分析'''：识别紧密互动的用户群体。
3. '''电路设计'''：分析信号传播路径的强连通性。

== 复杂度分析 ==
* 时间复杂度：<math>O(|V| + |E|)</math>（两次 DFS）。
* 空间复杂度：<math>O(|V|)</math>（存储逆序和转置图）。

== 扩展阅读 ==
* '''Tarjan 算法'''：通过单次 DFS 和栈维护实现，效率更高。
* '''Gabow 算法'''：类似 Tarjan，但使用不同栈管理方式。

{{Tip|理解 SCC 是学习更高级图算法（如 2-SAT 问题）的基础。}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]