强连通分量：双向通行的作战区块

强连通分量：双向通行的作战区块

「SCC」，强连通分量，Strongly Connected Component——工程圈里这个缩写的出场率高得惊人：编译器用它分析控制流，数据库用它优化递归查询，社交平台用它识别紧密互动的人群。它刻画的是有向图里"你来我往"的极大区块：块内任意两点双向可达，块与块之间只剩单向的干道。本节在上一节无向分量的基础上换到有向地形，讲透经典的 Kosaraju 两遍深度优先，并演练"缩点成骨架图"这个贯穿后续章节的操作。

区块的极大性

先立定义。有向图里，若顶点 u 与 v 双向可达（u 到 v 有通路，v 到 u 也有通路），称它们强连通。这同样是一个等价关系，等价类连同类内所有的边构成强连通分量；"极大"的含义是不存在另一个更大的强连通子图把它包含进去。

与无向情形的直观差异在于：两个强连通分量之间可以有边，但至多一个方向。假若甲块到乙块有边、乙块到甲块也有通路，那么沿块内互达性一拼接，两块其实同属一个更大的双向区块——与"极大"矛盾。这条看似不起眼的性质，正是"缩点之后必然无环"的来源：缩点图里若出现环，环上的各个分量又能互相抵达，又该合并。

Kosaraju 算法

求强连通分量的算法有多种，Kosaraju 的版本最利于理解，两遍深度优先加一次反转：

第一遍在原图上跑深度优先，记录每个顶点的完成时刻；第二遍把图的每条边全部反向得到反图，按完成时刻从大到小的次序在反图上发起深度优先，每轮访问到的白色顶点集合就是一个强连通分量。

为什么"反图加完成时刻倒序"恰好切出强连通分量？直觉版的论证抓两个事实。事实一：强连通分量内部的互达性与边的方向无关——正着走能到、反着走也能到，所以同一个分量在反图上仍是同一个分量，第二遍搜索不会把块切破。事实二：缩点图是无环的，分量之间存在"辈分"。第一遍搜索里，辈分高的分量（更靠近出口的）其顶点的完成时刻整体偏晚——就像出口处的房间总是先锁门。于是按完成时刻倒序访问，恰好先打入辈分最高的块；反图上从它出发的搜索被单向干道挡住，进不了别的块，收编的正是它自己。逐块蚕食，全图切分完毕。

代码演练

import networkx as nx

def kosaraju(G):
    """返回 顶点->分量编号 的映射"""
    # 第一遍：原图深度优先，收完成时刻
    finish, seen = [], set()
    for s in G.nodes:
        if s in seen:
            continue
        stack = [(s, iter(G[s]))]
        seen.add(s)
        while stack:
            u, it = stack[-1]
            advanced = False
            for v in it:
                if v not in seen:
                    seen.add(v)
                    stack.append((v, iter(G[v])))
                    advanced = True
                    break
            if not advanced:
                finish.append(stack.pop()[0])      # 弹栈即完成
    # 第二遍：反图上按完成时刻倒序
    RG = G.reverse(copy=True)
    comp, cid = {}, -1
    for s in reversed(finish):
        if s in comp:
            continue
        cid += 1
        stack = [s]
        comp[s] = cid
        while stack:
            u = stack.pop()
            for v in RG[u]:
                if v not in comp:
                    comp[v] = cid
                    stack.append(v)
    return comp

DG = nx.DiGraph([("a","b"),("b","c"),("c","a"),("c","b"),
                 ("a","c"),("d","e"),("e","d"),("c","f"),("e","a")])
comp = kosaraju(DG)
print("归属表:", comp)
# networkx 官方对照（内部用 Tarjan 思路）
print("nx 分量:", sorted(map(sorted, nx.strongly_connected_components(DG)), key=len))
​

第一遍里的显式栈写法值得留意：stack 里同时压顶点与其邻居迭代器，模拟递归的挂起与恢复，完成时刻在弹栈时记录——这正是上一章"时间戳比访问序值钱"的兑现处。跑完与 networkx 的结果对照，两个分量 {a,b,c} 与 {d,e}、外加孤行的 f，划分一致。

再演练缩点，把原图压缩成骨架：

def condense(G, comp):
    """按分量编号缩点，块内自环丢弃，返回骨架图"""
    skeleton = nx.DiGraph()
    for u, v in G.edges:
        cu, cv = comp[u], comp[v]
        if cu != cv:                    # 块间干道才保留
            skeleton.add_edge(cu, cv)
    return skeleton

sk = condense(DG, comp)
print("骨架的边:", list(sk.edges))
print("骨架无环吗:", nx.is_directed_acyclic_graph(sk))
print("骨架的拓扑序:", list(nx.topological_sort(sk)))
​

缩点之后的图必然无环——这由前面"块间至多单向"的性质直接保证。于是任何有向图，无论多纠缠，都能剥出一张棱角分明的骨架：块内细节完整保留，块间只剩先后与流向。第 6 章的拓扑排序在骨架上立即可用；反过来，处理"带环依赖"的调度问题（比如软件包的循环依赖）的标准手法，就是先缩点再排序，循环块单独拎出来人工裁决。

顺带交代同门兵器：Kosaraju 赢在思路通透，代价是两遍搜索加一次全图反转。生产实现更常用 Tarjan 的单遍版本——在深度优先的推进中维护一个栈与"可达最小编号"，回边把编号往回压，顶点弹栈的时机就是分量闭合的时机。它与第 3 章的时间戳装备一脉相承，一遍扫描同时拿到全部分量，常数与内存都更友好。两种算法输出同样的划分（分量划分唯一），选哪种看场合：教学与调试用 Kosaraju，性能敏感用 Tarjan。这个"划分唯一、算法多样"的局面与第 6 章的 Prim 与 Kruskal 如出一辙——结构量客观唯一，抵达它的路径从来不止一条。

⚠️ 常见坑：Kosaraju 第二遍忘了在反图上跑。在原图上按完成时刻倒序再搜一遍，得到的往往是不知所云的碎块——算法的对仗之美（正图记完成、反图取分量）恰是正确性所在。

💡 关键直觉：把强连通分量想成"铁板一块的作战单元"。单元内部怎么绕都行，单元之间只讲先后——这个压缩世界观在编译器（循环嵌套）、工作流引擎（环状审批）、社交网络（紧圈子）里全都适用。

区块圈定、骨架立起。还剩一类地形疑问：哪些路会绕回原地？下一节的环检测与并查集负责把回路一一排查出来。