连通分量、桥与割点

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. “连通”是什么意思

一个图称为连通的，是指它的每一对顶点之间都有一条路径。你可以从任意位置出发，沿着边走到任何地方。如果做不到，图就会分裂成若干部分，称为连通分量：它们是图中所含的极大连通子图，不同部分之间没有任何边。

理解连通分量最清楚的方式是借助关系“u 可以到达 v”。它是自反的（每个顶点通过空路径到达自身）、对称的（在无向图中，路径可以反向行走）和传递的（两条路径可以首尾相接）。具有这三个性质的关系称为等价关系，而每个等价关系都把它所在的集合划分成互不相交的类。可达关系的等价类恰好就是连通分量。这就是为什么每个顶点恰好属于一个连通分量，也是为什么一个没有任何边的孤立顶点自成一个连通分量。

一个图贯穿全文。它有十二个顶点和十三条边，其构造使得下面的每个概念都有一个具体的例子，并在需要时有一个具体的反例：

V = {A, B, C, D, E, F, G, H, I, J, K, L}
E = {AB, BC, CA, CD, DE, EC, EF, FG, GH, HI, IF, IJ, KL}        13 条边

连通分量 1 = {A, B, C, D, E, F, G, H, I, J}     12 条边
连通分量 2 = {K, L}                               1 条边

这些术语来自顶点与边指南。在第 11 节之前，本文讨论的全是无向图；到了第 11 节，边的方向会改变整个故事。

2. 求连通分量

由于连通分量就是可达关系的等价类，任何图搜索都能找出它们。从某个顶点开始一次广度优先或深度优先搜索；它到达的所有顶点就是该顶点所在的连通分量。然后从任一尚未到达的顶点重新开始，如此重复，直到没有剩余顶点。每一次新的起始就多出一个连通分量。

from collections import deque

def connected_components(graph):
    """给无向图的每个顶点标上其所在连通分量的编号。"""
    label, components = {}, []
    for start in graph:                      # 孤立顶点自成一个连通分量
        if start in label:
            continue
        label[start] = len(components)
        members, queue = [start], deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in label:
                    label[v] = len(components)
                    members.append(v)
                    queue.append(v)
        components.append(sorted(members))
    return components, label

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
graph = {v: [] for v in 'ABCDEFGHIJKL'}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

components, label = connected_components(graph)
print(len(components), components)
# 2 [['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'], ['K', 'L']]
print(label['H'] == label['A'], label['K'] == label['A'])
# True False

每个顶点只被标记一次，每条边被查看两次（从两端各一次），因此整个过程需要 O(V + E) 时间。遍历所有顶点的外层循环是关键的一行。单次搜索回答的是“从这里能到达什么”，而不是“一共有几个部分”；忘记这个循环是一种常见错误，会让一个有多个连通分量的图得出分量数为 1。

有两种替代方法值得了解。如果边是一条一条到来的，而且只增不删，那么并查集结构能以每条边接近常数的均摊时间维护当前的连通分量：每条边合并其两个端点所在的类，两个顶点属于同一连通分量，当且仅当它们有相同的根。这一思想可追溯到 Galler 和 Fischer 1964 年的等价算法。而在图像处理中，“图”是像素网格，同一个问题被称为连通分量标记。Rosenfeld 和 Pfaltz 在 1966 年为它描述了一种顺序扫描方法。是否把对角相邻的像素也算作邻居（称为 8 连通），还是只算上下左右四个邻居（称为 4 连通），会改变哪些形状算作一个区域、哪些算作两个。

甚至还有一个代数上的答案。图的拉普拉斯矩阵（对角线上是度数，每条边对应 −1）的特征值 0 的重数恰好等于连通分量的个数。对于贯穿全文的示例，这个重数是 2。特征值与结构之间的联系在谱图论中有详细展开。

3. 连通分量的个数说明了什么

记 n 为顶点数， m 为边数， k 为连通分量数。有几个事实把三者联系起来，它们可以用来检验任何统计连通分量的程序是否合理。

一个有 n 个顶点和 k 个连通分量的图至少有 n − k 条边，当且仅当它是森林时取等号。

证明是一个计数论证。从 n 个孤立顶点开始，也就是 n 个连通分量，然后逐条加入边。每条边要么连接两个不同的连通分量，使分量数减一，要么落在某个分量内部，什么也不改变。要降到 k 个连通分量，至少需要 n − k 条第一类的边，而当没有任何边被浪费在闭合环上时，恰好就是这么多条。森林恰好就是没有环的图，而树是连通的森林，这就是为什么一棵有 n 个顶点的树有 n − 1 条边，正如图论中的树一文用其他几种方法所证明的那样。贯穿全文的示例满足 13 ≥ 12 − 2 = 10，多出三条边，分别对应它的三个环。

另一个方向也有上限。一个有 k 个连通分量的简单图至多有 C(n − k + 1, 2) 条边，当把 n − k + 1 个顶点放进一个完全图、让其余 k − 1 个顶点保持孤立时取到上限。由此得到一个快速判定连通性的推论：一个边数超过 C(n − 1, 2) 的简单图不可能有两个连通分量，所以它必定是连通的。

还有一个事实是经典习题，证明只需两行：一个图与它的补图中，至少有一个是连通的。如果 G 不连通，任取两个顶点。如果它们位于 G的不同连通分量中，它们在补图中相邻。如果它们位于同一连通分量中，就从另一个分量中任取一个顶点；它在补图中与这两个顶点都相邻。无论哪种情况，它们都由一条长度至多为二的路径相连。这三个事实都已通过穷举验证，覆盖了所有至多六个顶点的简单图。

4. 桥：不能失去的边

连通性不仅关乎图是否连成一体，还关乎连得有多牢固。所谓桥，也称为割边，是指删去后会使连通分量数增加的边。删去它会把所在的连通分量恰好分成两部分，绝不会更多，因为删去一条边只能把它的两个端点彼此分开。

一条边是桥，当且仅当它不在任何环上。

如果边 uv 位于某个环上，环的其余部分就是从 u 到 v的第二条路线，所以删去这条边不会使任何东西断开。反过来，如果删去 uv 后 u 和 v 仍然连通，那么从 v 回到 u 的剩余路径加上 uv 就构成一个环。所以桥恰好是那些没有替代路线的边。由此立即得到两个推论：在树中，每条边都是桥；如果两个顶点之间还有第二条平行边，那么它们之间的边绝不是桥。

贯穿全文的示例有三条桥： E–F、 I–J 和 K–L。删去其中任意一条，连通分量数都会从 2 增加到 3。其他所有边都位于三个环之一上，即两个三角形和一个正方形。

5. 割点：不能失去的顶点

所谓关节点，也称为割点，是指连同其关联边一起删去后会使连通分量数增加的顶点。等价地说， v 是割点，当且仅当它所在的连通分量中存在另外两个顶点 u 和 w，使得每一条从 u 到 w 的路径都经过 v。

与桥不同，割点可以一次把所在的连通分量分成许多部分。删去一个有五片叶子的星图的中心，就剩下五个连通分量。在贯穿全文的示例中，删去 C 后剩下三个连通分量： {A, B}、从 D 到 J的所有顶点，以及 {K, L}（它本来就是分开的）。

桥与割点相互关联，而这种关联是一个值得仔细说明的陷阱：

• 桥的端点是割点，除非它的度为 1。删去 E，桥也随之消失，把 F 一侧与 D 一侧分开。这就是为什么 E、 F 和 I 都是割点。
• 桥的两端不一定有割点。 K–L 是一条桥，但两端的度都是 1，而删去一片叶子永远不会使任何东西断开。
• 割点不一定与任何桥相接。 C 连接两个三角形，这种形状常被称为蝴蝶图。与 C 相关联的每条边都位于一个三角形上，所以它们都不是桥，然而删去 C 会把 A 和 B 与其余部分切开。

因此贯穿全文的示例有四个割点： C、 E、 F 和 I，而这两个概念确实不同：顶点故障和链路故障暴露的是同一网络中不同的薄弱点。

6. 一次深度优先搜索同时找出两者

最直观的算法是依次删去每条边或每个顶点，然后重新统计连通分量。这样每个候选都要做一次完整的搜索，求桥需要 O(E(V + E)) 时间。1972 年和 1973 年，Tarjan 以及 Hopcroft 与 Tarjan 证明，一次深度优先搜索就足够了，总共只需 O(V + E) 时间。该方法依赖于每个顶点的两个数。

• disc[v] 是搜索第一次到达 v的时刻：第一个顶点为 0，下一个为 1，依此类推。
• low[v] 是从 v 的子树出发，先沿树边向下走，再至多经过一条回边，所能到达的最小发现时间。

在无向图的深度优先搜索中，每条非树边都是一条回边：它把一个顶点连到它的某个祖先。回边是一条逃生路线，一种不经过子树上方那条树边就能离开子树的途径。两个判定都在问这样的路线是否存在。对于从父节点 u 到子节点 v的树边：

桥        u–v 是桥            若  low[v] > disc[u]    v 下方没有顶点能到达 u 或更高处
割点      u 是割点              若  low[v] ≥ disc[u]    v 下方没有顶点能到达 u 之上
根        若根在 DFS 树中有 2 个或更多子节点，则根是割点

根需要单独的规则，因为它上方什么也没有：它把图分开，当且仅当搜索不得不两次离开它，这意味着它的各棵子树之间没有边。下面是完整的方法，以迭代方式编写，这样长路径就不会使 Python 的调用栈溢出：

def bridges_and_cut_vertices(vertices, edges):
    """Tarjan 的 low 值方法，迭代版本。边是 (u, v) 对；允许平行边。"""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):       # 记住边的编号，而不只是邻居
        adj[u].append((v, i))
        adj[v].append((u, i))
    disc, low, bridges, cuts, clock = {}, {}, [], set(), 0
    for root in vertices:
        if root in disc:
            continue
        disc[root] = low[root] = clock; clock += 1
        children = 0
        stack = [(root, -1, iter(adj[root]))]  # (顶点, 进入时所经边的编号, 邻居)
        while stack:
            u, in_edge, it = stack[-1]
            for v, i in it:
                if i == in_edge:             # 只跳过那一条边，而不是所有通往父节点的边
                    continue
                if v in disc:                # 回边：沿树向上的逃生路线
                    low[u] = min(low[u], disc[v])
                else:                        # 树边：向下深入
                    disc[v] = low[v] = clock; clock += 1
                    stack.append((v, i, iter(adj[v])))
                    break
            else:                            # u 已处理完：向其父节点 p 汇报
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]:
                        bridges.append(edges[in_edge])
                    if low[u] >= disc[p] and p != root:
                        cuts.add(p)
                    if p == root:
                        children += 1
        if children >= 2:                    # 根只有在拥有 2 个以上 DFS 子节点时才是割点
            cuts.add(root)
    return bridges, sorted(cuts), disc, low

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
bridges, cuts, disc, low = bridges_and_cut_vertices('ABCDEFGHIJKL', edges)
print(bridges)
# ['IJ', 'EF', 'KL']
print(cuts)
# ['C', 'E', 'F', 'I']

print(bridges_and_cut_vertices('xy', ['xy', 'xy'])[0])   # 重边不是桥
# []

在贯穿全文的示例中，从 A 开始的搜索恰好沿着一条路径一直向下走： A, B, C, …, J，三条非树边 C–A、 E–C 和 I–F 成为回边。下图显示了得到的数值。

把这张表与规则对照，就能得到所有答案。 low[F] = 5 大于 disc[E] = 4，所以 F 下方没有顶点能爬回 E，因此 E–F 是桥； I–J 出于同样的原因也是桥，因为 9 > 8。 low[D] = 2 等于 disc[C] = 2： C 下方的子树能爬回 C 本身，但不能更高，所以 C 是割点，尽管没有桥与它相接。而 A作为根只有一个子节点，所以它不是割点。

7. 能通过简单测试的两个错误

low 值代码很短，而它的两个经典错误在大多数小例子上都能给出正确答案。两者都已与穷举法对照检验：上面的版本在 5,000 个随机多重图上与“删去再重新统计”的结果完全一致。

跳过父顶点而不是父边。当搜索查看 v的邻居时，它不能把来时经过的树边当作回边，否则每个顶点都可以通过它自己的父节点逃脱。许多实现跳过“等于我父节点的那个邻居”。这在简单图中没有问题，但如果 x 和 y 之间有两条平行边，它会把两条都跳过，于是这条重边被报告为桥，尽管删去其中一条副本不会断开任何东西。按边的身份只跳过那一条边（代码中用 in_edge做的正是这件事），对于多重图也同样正确。

在回边上使用 low[w] 而不是 disc[w]。沿一条通往 w 的回边进行更新时，应当写作 disc[w]。写成 low[w] 会让逃生路线越过 w，继续经过属于另一个块的边。对于桥，这恰好无害：在 20,000 个随机图上，这个变体从未把桥判错。对于割点则不然：同样的测试在其中 35 个图上发现了它，而这次搜索找到的最小失败例子正是共享 C的那对三角形。使用 low[w]时，回边 E–C 引入了 low[C] = 0，所以 low[D] 变成 0，在 C 处的判定失败，这个割点就从输出中消失了。

8. 块与块割点树

割点把连通图分成若干自然的部分。所谓块，是指自身没有割点的极大连通子图：它要么是一个 2 连通的部分（删去任意一个顶点后仍然连通），要么是一条单独的桥，要么是一个孤立顶点。每条边恰好属于一个块，两个块至多共享一个顶点，而这个共享顶点就是割点。块也称为双连通分量，Hopcroft 和 Tarjan 1973 年的算法在同一次搜索中就能找出它们：维护一个边栈，每当割点判定成立时就弹出一个块。

贯穿全文的示例有六个块：三角形 {A, B, C} 和 {C, D, E}、正方形 {F, G, H, I}，以及三条桥 {E, F}、 {I, J} 和 {K, L}。

所谓块割点树，由 Harary 和 Prins 于 1966 年提出：它为每个块设一个节点，为每个割点也设一个节点，当割点位于某个块中时就在两者之间连一条边。对于连通图，它总是一棵树。对于连通分量 1，它有 5 个块节点和 4 个割点节点，共 9 个节点，由 8 条边相连。这棵树是图的粗略骨架：它不必查看任何块的内部，就能回答“哪些故障会把哪些部分分开”。

桥给出一种平行的分解。删去所有的桥，剩下的部分会分成若干 2 边连通分量，也就是能承受任意一条边失效的部分。示例中有五个： {A, B, C, D, E}、 {F, G, H, I}，以及单独的顶点 {J}、 {K} 和 {L}。注意，第一个是一个 2 边连通分量，却包含两个块。这个蝴蝶图能承受任意一条边的失效，却承受不了 C的失效。

两个经典定理解释了“没有割点”究竟带来了什么。Whitney 在 1932 年证明，至少有三个顶点的图是 2 连通的，当且仅当任意两个顶点之间都有两条没有公共内部顶点的路径，这等价于说任意两个顶点都位于同一个环上。Robbins 在 1939 年证明，连通图的边可以定向，使得每个顶点都能到达其他所有顶点，当且仅当这个图没有桥；这正是有向图与无向图指南的核心定理。

9. 衡量图的连通程度

桥和割点是阶梯的第一级。点连通度 κ(G) 是删去后使图不连通（或只剩一个顶点）的最少顶点数。边连通度 λ(G) 是删去后使图不连通的最少边数。至少有三个顶点的连通图有割点，当且仅当 κ = 1；至少有两个顶点的连通图有桥，当且仅当 λ = 1。Whitney 1932 年的不等式把两者都与最小度 δ(G)联系起来：

κ(G)  ≤  λ(G)  ≤  δ(G)

共享 C 的两个三角形          κ = 1   λ = 2   δ = 2      有割点，但没有桥
示例的连通分量 1             κ = 1   λ = 1   δ = 1      J 只靠一条边相连
任意环                       κ = 2   λ = 2   δ = 2

右边的不等式很容易：删去最小度顶点的所有关联边就能把它孤立。左边的不等式说明，顶点故障总是至少和边故障一样危险，而蝴蝶图表明这个差距确实可能存在。

Menger 1927 年的定理把这些最小值转化为最大值。使两个顶点 u 和 v 分离所需删去的最少边数，等于从 u 到 v 的两两没有公共边的路径的最大条数。顶点版本是同样的命题，只是换成内部不相交的路径，而且要求 u 和 v 不相邻，因为任何由其他顶点组成的集合都无法把两个相邻顶点分开。Menger 定理是最大流等于最小割的一个特例，而这也正是实践中计算连通度的方法。

10. 应用场景

连通分量、桥和割点是故障分析的基本词汇。只要一个系统可以建模为事物和它们之间的连接，这些概念就能指出它的薄弱点。

连通分量还解释了关于随机图最著名的结果之一。Erdős 和 Rényi 在 1960 年证明，如果向 n 个孤立顶点中随机加入边，连通分量会一直很小，直到平均度超过 1，然后会相当突然地出现一个巨分量，它包含所有顶点中的一个常数比例。这一相变在图论的历史一文中有介绍，它解释了为什么大型真实网络几乎总是有一个占主导地位的连通分量，周围散布着一些小分量。

当图不断变化时，连通性就成了一个数据结构问题。只有插入时，用并查集很容易处理。删除则难得多，因为删去一条边可能会、也可能不会分裂一个连通分量，而要弄清楚似乎需要一次搜索。Holm、de Lichtenberg 和 Thorup 在 2001 年证明，在同时支持插入和删除的情况下，连通性、2 边连通性和双连通性都可以维护，每次更新的均摊时间为多对数级。

11. 有向图：弱连通与强连通

在有向图中，“u 可以到达 v”不再是对称的，因此它不是等价关系，而“ v所在的分量”就需要做出选择。有两种标准的选择。

• 弱连通分量忽略方向：它们是底层无向图的连通分量，本文的所有内容都原封不动地适用于它们。
• 强连通分量要求双向可达。“u 到达 v 且 v 到达 u”又是一个等价关系，它的等价类就是强连通分量，可以用 Tarjan 或 Kosaraju 的算法在线性时间内求出，正如强连通分量指南所解释的。

在有向邻接表上运行无向图的连通分量代码，得到的既不是弱连通分量也不是强连通分量。它只沿边的正方向前进，所以它报告的“连通分量”取决于每次搜索恰好从哪里开始。要么先把邻接表对称化以得到弱连通分量，要么使用强连通分量算法。

12. 常见错误

13. 术语表

15. 参考文献

以上定义、定理和归属均出自以下文献，按时间顺序排列。

1. Menger, K. (1927). "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10，96 至 115 页。不相交路径与分离集。
2. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1)，150 至 168 页。
3. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2)，339 至 362 页。与上面的论文一起，给出点连通度、边连通度与最小度之间的不等式，以及用不相交路径对 2 连通图的刻画。
4. Robbins, H. E. (1939). "A Theorem on Graphs, with an Application to a Problem of Traffic Control." American Mathematical Monthly 46(5)，281 至 283 页。
5. Erdős, P. and Rényi, A. (1960). "On the Evolution of Random Graphs." Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5，17 至 61 页。巨分量。
6. Galler, B. A. and Fischer, M. J. (1964). "An Improved Equivalence Algorithm." Communications of the ACM 7(5)，301 至 303 页。用于合并等价类的并查集思想。
7. Harary, F. and Prins, G. (1966). "The Block-Cutpoint-Tree of a Graph." Publicationes Mathematicae Debrecen 13，103 至 107 页。
8. Rosenfeld, A. and Pfaltz, J. L. (1966). "Sequential Operations in Digital Picture Processing." Journal of the ACM 13(4)，471 至 494 页。图像的连通分量标记。
9. Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1(2)，146 至 160 页。
10. Hopcroft, J. E. and Tarjan, R. E. (1973). "Algorithm 447: Efficient Algorithms for Graph Manipulation." Communications of the ACM 16(6)，372 至 378 页。线性时间求双连通分量与割点。
11. Tarjan, R. E. (1974). "A Note on Finding the Bridges of a Graph." Information Processing Letters 2(6)，160 至 161 页。
12. Holm, J., de Lichtenberg, K. and Thorup, M. (2001). "Poly-logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity." Journal of the ACM 48(4)，723 至 760 页。
13. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。