强连通分量

Views: --

有向图中，若 uu 可达 vv 且 vv 也可达 uu，二者强连通。极大的两两强连通顶点集合称为强连通分量（SCC）。

1. 为什么 SCC 构成划分

“相互可达”满足自反、对称、传递，是等价关系，因此每个顶点恰好属于一个 SCC。一个分量内部可以互相绕行，不同分量之间则不能双向可达。

2. 缩点图一定是 DAG

把每个 SCC 压成一个超级顶点，保留分量间的有向边，得到凝聚图。

若凝聚图存在环，那么环上各分量可以相互到达，本应属于同一个更大的 SCC，与极大性矛盾。因此凝聚图必为 DAG。

这一事实是算法正确性的核心。

3. 转置图

转置图 GTG^T 把每条边反向：

(u,v)∈E  ⟺  (v,u)∈ET.(u,v)\in E\iff(v,u)\in E^T.

反向不会改变 SCC 内“相互可达”的关系，所以 GG 与 GTG^T 的 SCC 完全相同；只会把分量间 DAG 的边全部反过来。

4. Kosaraju 算法

  1. 在 GG 上做完整 DFS，记录顶点完成时间；
  2. 构造转置图 GTG^T；
  3. 按第一遍完成时间从大到小，在 GTG^T 上启动 DFS；
  4. 第二遍每棵 DFS 树恰好是一个 SCC。
order = vertices by decreasing finish time in DFS(G)
mark all vertices unvisited
for u in order:
    if u is unvisited:
        component = DFS(G_transpose, u)
        output component

5. 为什么第二遍不会串到别的分量

把第一遍 DFS 想象为在 SCC 缩点 DAG 上工作。完成时间最大的未处理分量，在转置后的缩点图中相当于一个不会通向其他未处理分量的源头。

所以从其中任一顶点在 GTG^T 做 DFS，只能覆盖该 SCC 内部；又因为分量内部仍强连通，它会覆盖整个 SCC。删去后同理继续。

注意算法版本可以交换 GG 与 GTG^T 的先后，但完成时间和第二遍图必须配套，不能只改一半。

6. 复杂度

构造转置图和两次 DFS 都是线性的：

T=O(V+E),S=O(V+E).T=O(V+E),\qquad S=O(V+E).

若同时维护正向和反向邻接表，转置图无需临时扫描重建。

7. Tarjan 算法

Tarjan 用一次 DFS、发现时间和 low 值在线识别 SCC，也能做到 O(V+E)O(V+E)。它实现更紧凑但不如 Kosaraju 直观。课程若重点是 DFS 完成时间与转置图，应优先掌握 Kosaraju 的证明链。

8. SCC 的典型应用

  • 判断有向图是否强连通；
  • 缩点后在 DAG 上做动态规划；
  • 识别互相依赖、无法单独拆开的模块；
  • 2-SAT 中判断变量与其否定是否落在同一 SCC；
  • 计算使图强连通需要补多少条边。

最后一类问题通常不是直接在原图上数边，而是先缩点，再看凝聚 DAG 的入度 0 与出度 0 分量。

评论