连通分量：清点势力范围

连通分量：清点势力范围

某天清晨，测绘官摊开刚侦察完的大区域地图，发现河流、沼泽与未探明地带把据点切成了好几片互不往来的人群聚落。远征队需要一份势力范围清单：整张地图分几块？某个据点属于哪块？两个据点是否同属一块？这正是图论里"连通分量"要回答的问题。本节承接上一章的遍历步法——深度优先每从白色顶点出发一次，就恰好收编一个完整分量——并把它升级为带标记的分量清点技术。它是后续一切"分块治理"策略的第一步。

从口语到定义

先把"连成一片"说精确。无向图里，若顶点 u 与 v 之间存在一条通路，就称它们连通。连通是顶点集上的等价关系：自己与自己连通（自反）、连通不分方向（对称）、连通可以接力（传递）。等价关系天然把顶点集切成互不重叠的等价类，每个等价类连同其内部的边构成一个连通分量。

这层"等价关系"的视角不卖弄抽象，它直接兑现成两条工程结论：其一，分量之间没有公共顶点，所以"给每个分量编号"是良定义的，编号本身就是一份从顶点到势力的映射；其二，判断"u 与 v 是否同块"不需要真去找路径，只需比对编号——把一次遍历的代价摊销成无数次查询，这是本章与第 10 章反复用到的技巧。

值得强调的边界情形：孤立顶点自成一个分量；分量数为一的图才叫连通图。"最多能分成几块"的答案是顶点数（全部孤立时），"最少"自然是一。分量数因此成为图最粗粒度的"碎裂程度"指标——第 10 章讲网络鲁棒性时，"删多少个顶点能把网络打成碎片"衡量的正是分量数的变化速度。

分量清点的实现

实现骨架是外层循环套遍历：扫一遍顶点表，见到白色顶点就发起新一轮深度优先，同时把这一轮访问到的所有顶点打上同一个分量编号：

import networkx as nx

def label_components(G):
    """返回 (分量数, 顶点->分量编号 的映射)"""
    comp = {}                       # 顶点 -> 编号
    cid = -1
    for start in G.nodes:           # 外层：扫全部顶点
        if start in comp:           # 已有归属，跳过
            continue
        cid += 1                    # 发现新分量
        stack = [start]             # 一轮显式栈深度优先
        comp[start] = cid
        while stack:
            u = stack.pop()
            for v in G[u]:          # 只在分量内部扩散
                if v not in comp:
                    comp[v] = cid
                    stack.append(v)
    return cid + 1, comp

archipelago = nx.Graph()
archipelago.add_edges_from([("A","B"),("A","C"),("C","D"),("B","D"),("E","F"),("F","G")])
archipelago.add_node("H")
n, comp = label_components(archipelago)
print("分量数:", n)
print("归属表:", comp)

def same_camp(comp, u, v):
    """同块查询：从'找路径'降级为'比对编号'"""
    return comp.get(u) == comp.get(v)

print("A 与 D 同块吗:", same_camp(comp, "A", "D"))
print("A 与 E 同块吗:", same_camp(comp, "A", "E"))
# networkx 官方实现对照
print("nx 分量列表:", sorted(map(sorted, nx.connected_components(archipelago))))
​

代码里有一个值得养成的习惯：写完自己的实现，立刻调 networkx 的官方版本对照输出。分量的划分是唯一的（等价关系保证），所以两边结果必须完全一致——这种"结果具有唯一性"的问题最适合用对照法自检。

把分量标记用到真实任务上。给定一张运输网，若两座仓库不在同一分量，任何调度方案都救不了它们的互通；明智的做法是先按分量切分，再在各分量内部单独优化：

def split_by_component(G):
    """把图按分量拆成子图列表"""
    n, comp = label_components(G)
    groups = {}
    for v, cid in comp.items():
        groups.setdefault(cid, []).append(v)
    return [G.subgraph(nodes).copy() for nodes in groups.values()]

for i, sub in enumerate(split_by_component(archipelago)):
    print(f"分量 {i}: {len(sub.nodes)} 个据点, {len(sub.edges)} 条道路")
​

这个"先切块、再逐块处理"的套路在第 10 章的社区发现里会以更精巧的形态重现——那里切的不再是硬边界分量，而是"连接密集"的软边界社区。

有向图的降级判定

把同样的定义搬到有向图会立刻碰壁：u 到 v 有路、v 到 u 却无路，算不算连通？有向图因此分裂出三级判定。若把所有边改成无向边后图连通，称弱连通；若任意两点至少单向可达，称单侧连通；若任意两点双向互达，称强连通。三者的强度依次递增，且强连通图必单侧连通、单侧连通必弱连通，反过来则都不成立。

def connectivity_grade(G):
    """判定有向图的连通级别：强/单侧/弱"""
    import itertools
    reach = dict(nx.all_pairs_shortest_path_length(G))   # 可达矩阵
    strong = all(v in reach[u] and u in reach[v]
                 for u, v in itertools.combinations(G.nodes, 2))
    if strong:
        return "强连通"
    one_side = all(v in reach[u] or u in reach[v]
                   for u, v in itertools.combinations(G.nodes, 2))
    if one_side:
        return "单侧连通"
    und = G.to_undirected()
    return "弱连通" if nx.is_connected(und) else "不连通"

one_way = nx.DiGraph([("哨所","渡口"),("渡口","大营"),("大营","哨所"),("渡口","仓库")])
print("级别:", connectivity_grade(one_way))
​

示例里，前一部分顶点构成互相可达的核心，仓库却只进不出——整图只拿到"单侧连通"。真正刻画"哪部分双向互达"的武器是下一节的强连通分量：它会把这些"你来我往"的作战区块一个个圈出来，再把区块之间的关系压缩成一张无环的骨架图。

⚠️ 常见坑：在调用无向图专用函数（比如 connected_components）前忘了检查图是否真的无向。networkx 对有向图调用无向版本会按弱连通处理，结果 silently 降级——这种错不会报异常，只会在数据里埋雷。

💡 关键直觉：连通分量是图的自同构不变量——换顶点编号、换绘制样式，分量划分纹丝不动。凡是"换汤不换药"的结构量，都值得优先计算，因为它们是图的指纹而非外衣。

势力范围已经圈定。下一节深入有向地形，看强连通分量如何把"双向互达"的区块圈出来，并把整张图压成一张棱角分明的骨架。