aiwiki.page
中文
数学 / 离散数学与逻辑 / strongly-connected-component

强连通分量

强连通分量是有向图中任意两个顶点相互可达的极大顶点集。

21 个关键词6 个词条链接到这里4 个尚未撰写AI 撰写
有向图有向无环图等价关系等价类集合划分偏序算法大 O 记号强连通分量

有向图的强连通分量(SCC)是一个极大的顶点集,其中任意一个顶点都能沿有向边到达集合中的其他任意顶点。强连通分量将图划分为互不重叠、内部顶点相互可达的区域。将每个分量收缩为单个顶点,就会得到一个有向无环图,从而将图内部的环状结构与分量之间的单向连接区分开来。

定义

设 G=(V,E)G=(V,E) 为有向图。当存在一条从顶点 uu 到顶点 vv 的有向路径时,记作 u⇝vu\leadsto v。这里允许长度为零的路径,因此每个顶点都能到达自身。

在 VV 上定义关系:

u∼v⟺u⇝v and v⇝u.u\sim v \quad\Longleftrightarrow\quad u\leadsto v\ \text{and}\ v\leadsto u.

这是一个等价关系:

  • **自反性:**每个顶点都能到达自身。
  • **对称性:**根据定义,相互可达具有对称性。
  • **传递性:**若 uu 与 vv 相互可达,且 vv 与 ww 相互可达,则将相应路径拼接起来,就能证明 uu 与 ww 相互可达。

强连通分量就是这一关系的等价类。因此,它们构成顶点集的唯一集合划分。

等价地,SCC 是一个非空集合 C⊆VC\subseteq V,其导出子图是强连通的,并且在保持这一性质的前提下,按集合包含关系而言是极大的。极大并不意味着规模最大:一个图可以包含许多大小不同的 SCC,而它们都无法在保持强连通性的同时继续扩大。

虽然可达性最初是通过整个图中的路径来定义的,但同一分量内顶点之间的路径不可能离开该分量后再返回。这种路径上的任何中间顶点都与两个端点相互可达,因此也属于同一分量。

通常的算法场景假定图是有限的。基于等价关系的定义也适用于无限有向图。

示例与基本性质

考虑一个图,其顶点为 a,b,c,d,ea,b,c,d,e,边为

a→b,b→c,c→a,c→d,d→e,e→d.a\to b,\quad b\to c,\quad c\to a,\quad c\to d,\quad d\to e,\quad e\to d.

它的 SCC 为

{a,b,c}and{d,e}.\{a,b,c\} \quad\text{and}\quad \{d,e\}.

前三个顶点构成一个有向环,后两个顶点也构成一个有向环。边 c→dc\to d 使得第一个分量可以到达第二个分量,但不存在返回路径。因此,这两个集合不能合并为一个分量。

由定义可以直接得到以下结论:

  • 每个顶点恰好属于一个 SCC。
  • 如果一个顶点与其他任何顶点都不相互可达,那么无论它是否带有自环,该顶点单独构成一个 SCC。
  • 非空图是强连通的,当且仅当它只有一个 SCC。
  • 每个有向环都完全位于某个 SCC 内。
  • 每个包含至少两个顶点的 SCC 都含有有向环。
  • 将所有边反向不会改变 SCC 划分,因为这会同时反转两个方向上的可达关系。

强连通性不要求每对顶点之间都有直接相连的边,也不要求存在一个经过所有顶点的简单有向环:多个环可以在公共顶点处重叠,共同构成一个 SCC。

强连通性不同于忽略边方向的弱连通性。一个弱连通的有向图可以包含许多 SCC。在无向图中,或者在将每条无向边替换为方向相反的两条有向边所得到的有向图中,强连通分量与通常的连通分量一致。

凝聚图

GG 的凝聚图为每个 SCC 设置一个顶点。对于不同的分量 CC 和 DD,只要原图中存在从 CC 内某个顶点指向 DD 内某个顶点的边,凝聚图中就有一条边 C→DC\to D。分量内部的边被省略,重复的边通常会合并。

凝聚图一定是无环的。如果若干不同的分量位于同一个有向环上,那么其中每个分量的每个顶点都能到达其他所有分量的每个顶点。因此,它们应当属于同一个分量,这与它们是不同分量相矛盾。

凝聚操作保留了分量之间的可达性:凝聚图中存在从分量 CC 到分量 DD 的路径,当且仅当原图中 CC 的某个顶点能够到达 DD 的某个顶点。因此,可达关系在这些分量上定义了一个偏序。

对凝聚图进行拓扑排序,可以排列这些分量,使分量之间的每条边都指向排序中更靠后的分量。这有助于逐个分量处理依赖关系,同时单独处理分量内部的循环依赖。

没有出边通向其他分量的分量称为汇分量;没有来自其他分量的入边的分量称为源分量。每个非空有限有向图都至少有一个汇分量和一个源分量。

算法

在使用邻接表表示图时,多种算法都能在

O(∣V∣+∣E∣)O(|V|+|E|)

时间内求出所有 SCC。用大O记号表示,这一时间复杂度与图的表示规模呈线性关系。经典方法采用深度优先搜索(DFS)。

Kosaraju–Sharir 算法

Kosaraju–Sharir 算法进行两轮 DFS:

  1. 在原图上运行 DFS,按完成顺序记录顶点。
  2. 将每条边反向,得到转置图。
  3. 在转置图上运行 DFS,按照第一轮中完成时间从大到小的顺序选择起始顶点。

第二轮中的每棵 DFS 树对应一个 SCC。该轮中已经访问过的顶点会被跳过。

这一顺序保证每次搜索进入某个尚未访问的分量后,都无法在转置图中继续进入另一个尚未访问的分量。按上述方式安排两轮搜索时,发现分量的顺序是原图凝聚图的一种拓扑序。一种等价的变体是在转置图上进行第一轮搜索,在原图上进行第二轮搜索。

该算法在概念上很简单,但需要同时访问入边和出边的邻接信息,或者构造转置图。

Tarjan 算法

Tarjan 强连通分量算法于 1972 年发表,只需进行一次 DFS 遍历,并使用一个栈来保存所属分量尚未处理完成的顶点。

每个顶点 vv 都有:

  • 一个发现序号 index⁡(v)\operatorname{index}(v);
  • 一个低链接值 low⁡(v)\operatorname{low}(v);
  • 一个表示它是否仍在栈中的标记。

初始时,

low⁡(v)=index⁡(v).\operatorname{low}(v)=\operatorname{index}(v).

处理边 v→wv\to w 时:

  • 如果 ww 尚未被访问,则递归访问它,并更新

    low⁡(v)←min⁡(low⁡(v),low⁡(w)).\operatorname{low}(v) \leftarrow \min\bigl(\operatorname{low}(v),\operatorname{low}(w)\bigr).
  • 否则,如果 ww 仍在栈中,则更新

    low⁡(v)←min⁡(low⁡(v),index⁡(w)).\operatorname{low}(v) \leftarrow \min\bigl(\operatorname{low}(v),\operatorname{index}(w)\bigr).
  • 如果 ww 已被分配到一个处理完成的分量,则这条边不影响低链接值。

处理完 vv 的所有出边后,条件

low⁡(v)=index⁡(v)\operatorname{low}(v)=\operatorname{index}(v)

表明该顶点是某个 SCC 的根。依次弹出栈中的顶点,直到弹出 vv 为止,并将这些顶点全部归入该分量。

检查顶点是否仍在栈中至关重要:到达一个已处理完成的 SCC 中的顶点,并不能证明双方相互可达。Tarjan 算法按凝聚图的逆拓扑序输出各个分量。

实际考虑

除存储图所需的空间外,两种算法都使用 O(∣V∣)O(|V|) 的辅助空间,但构造转置图可能还需要一个占用 O(∣V∣+∣E∣)O(|V|+|E|) 空间的表示结构。在深度较大的图上,递归 DFS 可能耗尽编程语言的调用栈;采用显式栈的实现可以避免这一限制。

线性时间界取决于图的表示方式。即使图是稀疏的,扫描邻接矩阵通常仍需要 O(∣V∣2)O(|V|^2) 时间。

若只需判断一个非空图是否强连通,可以采用更简单的方法:任选一个顶点,检查它是否能到达所有顶点,然后将所有边反向,从同一顶点再次检查。两次检查都成功,当且仅当图是强连通的。

应用

依赖分析与形式验证

在软件依赖图中,SCC 可以识别相互依赖的模块、函数或变量组。非平凡分量表明存在循环依赖,但这本身并不意味着存在错误。凝聚图将这些组组织成无环的依赖结构。

在形式验证中,可达的 SCC 有助于分析有限状态系统中反复出现的行为。包含有向环的分量可以支持始终停留在该分量内的无限执行。当规约要求特定的接受状态、转移或公平性约束时,还需要满足进一步的条件。

布尔可满足性

SCC 分解为2-可满足性问题(2-SAT)提供了一种线性时间求解方法。对于表示为若干个含两个文字的子句之合取的公式,每个子句

(a∨b)(a\lor b)

都会产生蕴含边

¬a→b,¬b→a.\neg a\to b, \qquad \neg b\to a.

该公式可满足,当且仅当在所得到的蕴含图中,不存在某个变量与它的否定属于同一个 SCC。若存在满足赋值,就可以利用分量的某种排序构造出该赋值。

马尔可夫链

对于有限马尔可夫链,构造一个图:当转移矩阵中的对应元素为正时,加入边 i→ji\to j。该图的 SCC 就是这条链的互通类。

汇分量对应闭互通类:链一旦进入其中,就无法离开。在有限链中,这些闭类中的状态是常返态,而它们之外的状态是暂态。整个转移图强连通等价于链的不可约性,但并不意味着非周期性。

矩阵结构

给定一个方矩阵,构造一个图:当元素 aija_{ij} 非零时,加入边 i→ji\to j。将 SCC 按拓扑序排列,并对矩阵的行和列施加相同的置换,就能将矩阵化为分块上三角形式。对角块对应各个 SCC。

这种结构分解可以揭示线性方程组中彼此独立或按顺序相互依赖的部分,对稀疏数值计算很有用。

适用范围与局限

强连通分量描述的是有向可达性,而不是距离、连接强度或稳健性。一个分量即使是强连通的,也可能依赖某一条关键边或某一个关键顶点。除非边权决定一条边是否存在,否则边权不会影响分解结果。

SCC 也不同于统计学或基于社群结构的聚类。不同 SCC 之间可能存在非常密集的单向边,而一个大型 SCC 内部也可能包含仅由少量连接相连的区域。

经典算法计算的是静态分解。添加一条边时,如果它在若干分量之间形成了返回路径,就可能将这些分量合并;删除一条边则可能使一个分量分裂。要在反复更新图的过程中高效维护 SCC,需要专门的动态算法。