连通性：图能拆成几块？

上一篇我们建立了 BFS 和 DFS 两种基本遍历工具，尤其是 DFS 的时间戳（发现时间 $d$ 、结束时间 $f$ ）和括号定理。现在我们进入 Part 1”探”的第二站：用这些工具分析图的全局连通结构。

拿到一张复杂的图——比如一个大型社交网络、一个电力系统拓扑——你最先需要回答的问题不是”A 到 B 最近多远”或”谁最重要”，而是更基础的：这张图能拆成几个互不相连的块？哪些节点和边是”粘合剂”——删掉它们整个网络就会断裂？哪些节点之间存在强连通关系（你能到我，我也能到你）？没有连通性分析，你甚至不知道两个节点之间是否存在路径，后续的最短路径、社区发现、网络流等问题都无从谈起。

算法范式：穷举搜索（DFS 衍生）——系统地访问所有可能，通过 DFS 时间戳和 low-link 值分析结构

核心思想：DFS 时间戳 + low-link 是统一工具

在深入各个具体问题之前，先抓住一个核心洞察：

本文所有算法——连通分量、桥、割点、双连通分量、强连通分量——都基于同一个工具：DFS 的时间戳和 low-link 值。

回顾 Art. 1：DFS 为每个节点 $v$ 记录发现时间 $\text{disc}[v]$ 和结束时间 $f[v]$ 。现在我们引入一个新概念：

low-link 值 $\text{low}[v]$ ：从 $v$ 出发，通过 DFS 树中的后代边（tree edges）和至多一条回边（back edge），能到达的最早被发现的节点的发现时间。

$\text{low}[v] = \min\!\bigl(\text{disc}[v],\;\min_{(u,w) \text{ is back edge in subtree of } v} \text{disc}[w]\bigr)$

直觉上， $\text{low}[v]$ 衡量的是”从 $v$ 的子树出发，能绕回多高的祖先”。如果 $\text{low}[v]$ 很小（能绕到很高的祖先），说明即使删掉 $v$ 到它父亲的那条树边， $v$ 的子树仍能通过回边保持连通。反之，如果 $\text{low}[v] = \text{disc}[v]$ （只能回到自己），说明 $v$ 的子树和上方之间只有一条通道——那条树边就是桥。

这个简单的定义是整篇文章的核心武器。

无向图连通性

连通分量（Connected Components）

最简单的连通性问题：无向图有几个互不相连的”岛屿”？

定义：无向图 $G = (V, E)$ 的一个连通分量（connected component）是一个极大的连通子图——其中任意两个节点之间都存在路径，且不能再加入更多节点而保持连通。

算法：极其简单——对每个未访问的节点启动一次 BFS 或 DFS，每次能访问到的所有节点构成一个连通分量。

ConnectedComponents(G):
    count = 0
    for each v ∈ V:
        if not visited[v]:
            count += 1
            BFS(G, v)  // 或 DFS(G, v)
            // 将本次访问到的所有节点标记为第 count 个分量

复杂度： $O(n + m)$ 时间， $O(n)$ 空间。每个节点和每条边恰好被访问一次。

连通分量的计算看似trivial，但它是所有后续分析的前提——如果两个节点不在同一个连通分量中，它们之间不存在路径。

桥（Bridge）与割点（Articulation Point）

连通分量告诉你”图分成几块”，但更有价值的问题是：图中哪些连接是脆弱的？ 删除哪条边或哪个节点会导致图不再连通？

定义：

桥（bridge）：无向图中的一条边 $e$ ，删除后连通分量数量增加。等价地： $e$ 不在任何环上。
割点（articulation point, AP）：无向图中的一个节点 $v$ ，删除 $v$ 及其所有关联边后，连通分量数量增加。

为什么它们重要？ 桥和割点是网络的”单点故障”——在通信网络中，桥是关键链路，割点是关键路由器；在社交网络中，割点是连接不同社区的”桥梁人物”。找出它们，才能设计冗余拓扑来增强鲁棒性。

Tarjan 的桥和割点算法

Robert Tarjan 在 1972 年的经典论文中给出了 $O(n + m)$ 时间找出所有桥和割点的算法，核心就是 DFS + low-link。

桥的判定

定理（Tarjan, 1972）：在 DFS 树中，边 $(u, v)$ （ $u$ 是 $v$ 的父亲）是桥，当且仅当 $\text{low}[v] > \text{disc}[u]$ 。

直觉： $\text{low}[v] > \text{disc}[u]$ 意味着 $v$ 的整棵子树中，没有任何回边能到达 $u$ 或 $u$ 的祖先。因此删除树边 $(u, v)$ 后， $v$ 的子树和图的其余部分就完全断开了。

算法步骤：

对图做 DFS，计算每个节点的 $\text{disc}[v]$ 和 $\text{low}[v]$
对每条 DFS 树边 $(u, v)$ $(u, v)$ （ $u$ $u$ 是父亲， $v$ $v$ 是子节点），检查：
- 如果 $\text{low}[v] > \text{disc}[u]$ ，则 $(u, v)$ 是桥

low-link 的计算（无向图版本）：

DFS-Bridge(u, parent):
    disc[u] = low[u] = timer++
    for each v ∈ N(u):
        if v == parent:
            continue              // 忽略来时的边
        if disc[v] == -1:         // 未访问：树边
            DFS-Bridge(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > disc[u]:
                output "(u, v) is a bridge"
        else:                     // 已访问：回边
            low[u] = min(low[u], disc[v])

逐项理解：

disc[u] = low[u] = timer++：初始时， $v$ 能到达的最早节点就是自己
low[u] = min(low[u], low[v])：子节点能绕回多高，父节点也能（沿树边过去再绕回来）
low[u] = min(low[u], disc[v])：遇到回边，直接更新能到达的最早祖先
if low[v] > disc[u]：如果子节点的子树无法绕回 $u$ 或更高，这条树边就是桥

割点的判定

定理：DFS 树中的节点 $u$ 是割点，当且仅当满足以下条件之一：

$u$ 是根节点，且 $u$ 有 $\geq 2$ 个 DFS 子树（即 $u$ 在 DFS 树中的子节点数 $\geq 2$ ）
$u$ 不是根节点，且存在某个子节点 $v$ 使得 $\text{low}[v] \geq \text{disc}[u]$

直觉：

条件 1：根节点如果只有一个子树，删掉它后子树仍然连通（只是少了根）。但如果有两个以上子树，删掉根后子树之间就断开了。
条件 2（注意是 $\geq$ 而非 $>$ ）： $\text{low}[v] \geq \text{disc}[u]$ 意味着 $v$ 的子树无法绕到 $u$ 的”上方”—— $v$ 的子树连接到图其余部分的唯一通道经过 $u$ 。注意和桥的区别：桥是 $>$ （严格），割点是 $\geq$ ，因为即使 $v$ 能绕回 $u$ 本身（ $\text{low}[v] = \text{disc}[u]$ ），删掉 $u$ 后 $v$ 的子树仍然断开。

复杂度：桥和割点的算法都是在一次 DFS 中完成，时间 $O(n + m)$ ，空间 $O(n)$ 。

数值走查：桥与割点

用上面 low-link 图中的例子验证。图有 6 个节点 A-F，DFS 从 A 出发：

节点	disc	low	说明
A	1	1	根节点
B	2	1	通过 C→D→A 的回边，low 更新为 1
C	3	1	通过 D→A 的回边，low 更新为 1
D	4	1	回边到 A，low = min(4, disc[A]=1) = 1
E	5	5	无回边，low 保持 5
F	6	6	无回边，low 保持 6

桥检查：

树边 (A,B)：low[B]=1，disc[A]=1， $1 \not> 1$ → 不是桥 ✓（有环 A-B-C-D-A 保护）
树边 (B,C)：low[C]=1，disc[B]=2， $1 \not> 2$ → 不是桥 ✓
树边 (C,D)：low[D]=1，disc[C]=3， $1 \not> 3$ → 不是桥 ✓
树边 (B,E)：low[E]=5，disc[B]=2， $5 > 2$ → 是桥 ✓
树边 (E,F)：low[F]=6，disc[E]=5， $6 > 5$ → 是桥 ✓

割点检查：

A 是根，只有一个 DFS 子树（B）→ 不是割点
B 不是根。子节点 C：low[C]=1 < disc[B]=2 → 不满足。子节点 E：low[E]=5 ≥ disc[B]=2 → 是割点 ✓（删掉 B，E 和 F 就断开了）
E 不是根。子节点 F：low[F]=6 ≥ disc[E]=5 → 是割点 ✓

双连通分量（Biconnected Components）

桥和割点给出了”脆弱连接”的位置。更精细的分析是：以割点为分界，把图拆成双连通分量。

定义：无向图的一个双连通分量（biconnected component, BCC）是一个极大子图，其中任意两个顶点之间存在至少两条顶点不相交的路径。等价地：BCC 内部没有割点。

关键性质：

每条边恰好属于一个 BCC
割点可以属于多个 BCC（它们是 BCC 之间的”铰链”）
只有一条边的 BCC 就是一座桥

算法：在找割点的 DFS 过程中维护一个边的栈。当发现一个割点或回到根节点时，弹栈直到当前树边，弹出的所有边构成一个 BCC。时间仍为 $O(n + m)$ 。

有向图连通性

无向图中”连通”的定义很直观——两点之间有路径就行。但在有向图中，“可达性”不是对称的：你能到达我，不意味着我能到达你。这催生了更丰富的连通性概念。

强连通分量（Strongly Connected Components, SCC）

定义：有向图 $G = (V, E)$ 的一个强连通分量是一个极大节点子集 $S \subseteq V$ ，使得 $S$ 中任意两个节点 $u, v$ 之间都存在 $u \to v$ 和 $v \to u$ 的有向路径。

换句话说：SCC 内部的节点”互相可达”。SCC 是有向图的基本结构单元。

找 SCC 有两个经典的 $O(n + m)$ 算法：Tarjan 算法和 Kosaraju 算法。两者都基于 DFS，但思路不同。

Tarjan 的 SCC 算法

Tarjan 的 SCC 算法和他的桥/割点算法使用相同的核心工具——DFS + low-link——但 low-link 的定义略有不同。

核心思想：

做一次 DFS，维护一个栈存放”当前路径上和尚未归属任何 SCC 的节点”
对每个节点计算 $\text{disc}[v]$ 和 $\text{low}[v]$
当 DFS 回溯到一个节点 $u$ 时，如果 $\text{low}[u] = \text{disc}[u]$ ，说明 $u$ 是某个 SCC 的”根”——从栈顶弹出节点直到弹出 $u$ ，弹出的所有节点构成一个 SCC

有向图中 low-link 的更新规则（与无向图的关键区别）：

遇到树边 $(u, v)$ ：递归访问 $v$ 后， $\text{low}[u] = \min(\text{low}[u], \text{low}[v])$
遇到指向栈中节点 $v$ 的边（回边或横跨边到栈中节点）： $\text{low}[u] = \min(\text{low}[u], \text{disc}[v])$
遇到指向已属于其他 SCC 的节点 $v$ （不在栈中）：不更新。这是关键——已经弹出栈的节点已经”封闭”了，不再参与当前 SCC 的构建

Tarjan-SCC(G):
    timer = 0
    S = empty stack
    for each v ∈ V:
        if disc[v] is undefined:
            StrongConnect(v)

StrongConnect(u):
    disc[u] = low[u] = timer++
    S.push(u); onStack[u] = true

    for each (u, v) ∈ E:
        if disc[v] is undefined:
            StrongConnect(v)
            low[u] = min(low[u], low[v])
        else if onStack[v]:
            low[u] = min(low[u], disc[v])

    // If u is SCC root
    if low[u] == disc[u]:
        SCC = {}
        repeat:
            w = S.pop(); onStack[w] = false
            SCC = SCC ∪ {w}
        until w == u
        output SCC

为什么 $\text{low}[u] = \text{disc}[u]$ 意味着 SCC 根？

$\text{low}[u] = \text{disc}[u]$ 意味着从 $u$ 的子树出发，无法通过任何回边到达 $u$ 上方的祖先。但 $u$ 的子树中可能有回边指回 $u$ 或 $u$ 的后代——这些节点形成了一个”闭合回路”，就是 SCC。栈中从 $u$ 到栈顶的节点，恰好就是这个 SCC 的成员。

Tarjan SCC 走查

下面的交互组件展示 Tarjan 算法在一个 8 节点有向图上的完整执行过程。注意观察 disc/low 值的更新和栈的变化。

Tarjan SCC 算法走查有向图 · 8 节点 · 3 个 SCC

步骤 1/30: 初始状态：所有节点未访问。Tarjan 算法将用一次 DFS 找出所有 SCC。

1 / 30

仔细观察几个关键时刻：

当 DFS 遇到 C→A 的回边时，low 值沿着 C、B 一路传播回 A，使得整个 $\lbrace A,B,C \rbrace$ 的 low 值都变成 disc[A]
当 DFS 从 C 回溯到 A 时，发现 low[A] = disc[A]，于是弹栈找到 SCC₁ = $\lbrace A,B,C \rbrace$
同样的过程在 $\lbrace D,E,F \rbrace$ 和 $\lbrace G,H \rbrace$ 上重复

Kosaraju 算法

Kosaraju 算法用完全不同的思路找 SCC，但同样是 $O(n + m)$ 。它的优美之处在于概念上更容易理解。

核心思想：对图做两遍 DFS——

第一遍：在原图 $G$ 上做 DFS，按结束时间 $f$ 的递减顺序排列节点
第二遍：构建反图 $G^R$ （所有边反向），按第一遍得到的顺序在 $G^R$ 上做 DFS——每次 DFS 能访问到的节点恰好构成一个 SCC

为什么两遍 DFS 能找 SCC？

关键洞察：反转所有边后，SCC 内部的连通性不变（如果 $u \to v$ 且 $v \to u$ ，反转后仍然是 $v \to u$ 且 $u \to v$ ），但 SCC 之间的边方向反转了。

第一遍 DFS 的结束时间保证了：如果 SCC₁ 有边指向 SCC₂，那么 SCC₁ 中至少有一个节点的结束时间大于 SCC₂ 中所有节点的结束时间。

因此第二遍在反图上按结束时间递减顺序 DFS 时：

先处理”最上游”的 SCC（在原图中没有入边从其他 SCC 进来的）
反图中从该 SCC 出发的边（原图中指向它的边）不会到达其他 SCC——因为那些 SCC 在原图中是”下游”
所以每次 DFS 恰好访问一个完整的 SCC，不多不少

复杂度：两遍 DFS + 一次图反转 = $O(n + m)$ 时间， $O(n + m)$ 空间（需要存储反图）。

Tarjan vs Kosaraju

维度	Tarjan	Kosaraju
DFS 遍数	1 遍	2 遍
额外空间	栈 + onStack 数组， $O(n)$	反图 $G^R$ ， $O(n + m)$
时间复杂度（最坏）	$O(n + m)$	$O(n + m)$
实现难度	较高（low-link 更新规则需仔细）	较低（两遍标准 DFS）
概念直觉	基于 low-link 的”闭合检测”	基于”反图中 SCC 内连通性不变”
实际常数	更小（一遍 DFS）	更大（两遍 + 反图构建）

选择建议：如果只需要 SCC，两者都好。竞赛中 Tarjan 更常用（一遍更快）。工程中 Kosaraju 更容易调试（两遍标准 DFS，逻辑清晰）。

缩点（Condensation）：SCC → DAG

找到所有 SCC 后，一个自然的操作是缩点：将每个 SCC 缩成一个”超级节点”，SCC 之间的边变成超级节点之间的边（去重）。

定理：缩点后的图一定是 DAG（有向无环图）。

证明：如果缩点图有环 $S_1 \to S_2 \to \cdots \to S_k \to S_1$ ，那么 $S_1$ 中的任意节点能到达 $S_2$ 中的任意节点（通过 SCC 内连通 + SCC 间边），以此类推， $S_1$ 到 $S_k$ 到 $S_1$ 都互相可达——这意味着 $S_1 \cup S_2 \cup \cdots \cup S_k$ 应该是同一个 SCC，与”它们是不同 SCC”矛盾。

缩点的意义：

将”有环的复杂有向图”转化为”无环的 DAG”
DAG 可以拓扑排序（Art. 3 的主题）
许多有向图上的问题，先 SCC 缩点再在 DAG 上解决，会大大简化

2-SAT：SCC 的经典应用

SCC 不只是一个理论概念——它有一个极其优雅的应用：2-SAT（2-satisfiability，2-可满足性问题）。

问题定义

给定 $n$ 个布尔变量 $x_1, x_2, \ldots, x_n$ ，以及 $m$ 个子句（clause），每个子句是两个文字（literal）的析取（OR）：

$(a_1 \lor b_1) \land (a_2 \lor b_2) \land \cdots \land (a_m \lor b_m)$

其中每个 $a_i, b_i$ 是某个 $x_j$ 或 $\neg x_j$ 。问：是否存在一组赋值使得所有子句同时为真？如果存在，给出一组解。

例子： $(x_1 \lor x_2) \land (\neg x_1 \lor x_3) \land (\neg x_2 \lor \neg x_3)$ 。

注意：3-SAT（每个子句 3 个文字）是 NP-complete 的，但 2-SAT 可以在 $O(n + m)$ 时间内求解！关键就在于 SCC。

蕴含图构造

每个子句 $(a \lor b)$ 等价于两条蕴含（implication）：

$\neg a \Rightarrow b \quad \text{和} \quad \neg b \Rightarrow a$

（如果 $a$ 为假，则 $b$ 必须为真；如果 $b$ 为假，则 $a$ 必须为真。）

对每个变量 $x_i$ 创建两个节点 $x_i$ 和 $\neg x_i$ 。每条蕴含变成一条有向边。这样我们得到一个 $2n$ 个节点、 $2m$ 条边的有向图——蕴含图（implication graph）。

SCC 判定与求解

定理（Aspvall, Plass & Tarjan, 1979）：2-SAT 公式可满足，当且仅当对于每个变量 $x_i$ ， $x_i$ 和 $\neg x_i$ 不在蕴含图的同一个 SCC 中。

直觉：如果 $x_i$ 和 $\neg x_i$ 在同一个 SCC 中，意味着 $x_i \Rightarrow \cdots \Rightarrow \neg x_i$ 且 $\neg x_i \Rightarrow \cdots \Rightarrow x_i$ ——无论 $x_i$ 取真还是假，都能推导出它必须取相反值，矛盾。

求解方法：

构建蕴含图
用 Tarjan 或 Kosaraju 求所有 SCC
检查：对每个 $i$ ，如果 $x_i$ 和 $\neg x_i$ 在同一 SCC → 不可满足
否则，对 SCC 的缩点 DAG 做拓扑排序。对每个变量 $x_i$ $x_{i}$ ：
- 如果 $x_i$ 所在 SCC 的拓扑序在 $\neg x_i$ 之后 → $x_i = \text{true}$
- 否则 → $x_i = \text{false}$

复杂度： $O(n + m)$ ——构建蕴含图 $O(m)$ ，SCC $O(n + m)$ ，拓扑排序 $O(n + m)$ 。

应用场景

连通性分析的工具在多个领域都有直接应用。

社交网络脆弱节点

在社交网络中，割点是连接不同社区的”桥梁人物”——只有通过他们，两个社区才能交流。Facebook 的一项研究发现，大规模社交图中约 1-3% 的用户是割点，删除他们会显著增加图的碎片化程度（参见 Backstrom et al., Facebook 网络结构研究）。

识别这些关键节点对于社区管理、信息传播优化、以及理解网络鲁棒性都至关重要。

电力与通信网络

桥是电力网络中的关键传输线路。2003 年北美大停电事件中，关键输电线路（相当于网络图中的”桥”）的连续故障导致级联崩溃，5500 万人受影响。

通过连通性分析找出网络中的桥和割点，网络工程师可以针对性地增加冗余链路，确保 $\kappa(G) \geq 2$ （顶点连通度（vertex connectivity） $\kappa(G)$ ：使图不连通需要删除的最少节点数——至少为 2 意味着不存在割点，网络更健壮）。

编译器优化：循环依赖检测

编译器分析模块之间的依赖关系时，循环依赖对应有向图中的 SCC。SCC 缩点后得到 DAG，DAG 的拓扑排序就是合法的编译顺序。

实例：Rust 编译器 (rustc) 使用 SCC 分析 trait 系统中的循环引用；LLVM 在 loop analysis pass 中使用 Tarjan 算法识别循环结构。

布尔求解器

2-SAT 在硬件验证、配置管理、时序约束系统等领域广泛应用。例如，在 VLSI 设计中，某些时钟信号约束可以建模为 2-SAT 并用蕴含图 + SCC 高效求解。

复杂度对比表

算法	时间复杂度（最坏）	空间复杂度	适用场景
连通分量（BFS/DFS）	$O(n + m)$	$O(n)$	无向图分块
桥和割点（Tarjan）	$O(n + m)$	$O(n)$	无向图脆弱点检测
双连通分量	$O(n + m)$	$O(n + m)$	无向图精细分块
SCC — Tarjan	$O(n + m)$	$O(n)$	有向图强连通分析
SCC — Kosaraju	$O(n + m)$	$O(n + m)$	有向图强连通分析
缩点（Condensation）	$O(n + m)$	$O(n + m)$	有环有向图 → DAG
2-SAT	$O(n + m)$	$O(n + m)$	布尔可满足性

所有算法都是线性时间——这是 DFS 作为基础工具的威力。图有多大，算法就走多久，不多不少。

🔁 迭代机器视角 — Tarjan SCCEQ: 方程 / 不动点

low(v) = min(disc(v), min_w low(w))

Graph	有向图
State[v]	disc, low, onStack
SELECT	LIFO (DFS)
COMBINE	DFS 树边/回边更新 low-link
重入	无
TERMINATE	Frontier 空 + 栈检查
求解方法	FI

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — Kosaraju SCCSTR: 结构计算

Graph	原图 + 转置图
State[v]	visited + component ID
SELECT	LIFO（两次 DFS）
COMBINE	第一次 DFS 后序，第二次在转置图上 DFS
重入	无
求解方法	FI

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文展示了 DFS 时间戳和 low-link 值如何成为分析图连通结构的统一工具：

无向图：连通分量（BFS/DFS）→ 桥与割点（low-link）→ 双连通分量
有向图：强连通分量 SCC（Tarjan / Kosaraju）→ 缩点得 DAG
SCC 应用：2-SAT 的蕴含图判定 + 求解
统一思想： $\text{low}[v]$ 衡量”从子树能绕回多高”——这一个概念就撑起了桥、割点、BCC、SCC 四个问题
全部 $O(n + m)$ ：线性时间，无需更复杂的数据结构

连通性分析回答了”图的全局结构是什么样的”这个基础问题。而 SCC 缩点给我们留下了一个重要线索：缩点后得到的 DAG 能做什么？ 下一篇 Art. 3: 拓扑排序与 DAG 将展开这个话题——DAG 上的拓扑排序是调度、依赖分析和动态规划的基石。

实现指引

算法	库	函数/方法
连通分量	NetworkX	`nx.connected_components(G)`
桥	NetworkX	`nx.bridges(G)`
割点	NetworkX	`nx.articulation_points(G)`
双连通分量	NetworkX	`nx.biconnected_components(G)`
SCC（强连通分量）	NetworkX	`nx.strongly_connected_components(G)`
SCC — Kosaraju	NetworkX	`nx.kosaraju_strongly_connected_components(G)`
缩点（Condensation）	NetworkX	`nx.condensation(G)`
连通分量	scipy	`scipy.sparse.csgraph.connected_components(graph)`
SCC	scipy	`scipy.sparse.csgraph.connected_components(graph, directed=True)`
连通分量 / SCC	igraph	`g.connected_components()`, `g.clusters()`
桥 / 割点	igraph	`g.bridges()`, `g.articulation_points()`