aiwiki.page
中文
计算机 / 算法与理论 / kosaraju-sharir-algorithm

Kosaraju–Sharir 算法

Kosaraju–Sharir 算法通过两遍深度优先搜索求出有向图的强连通分量,采用邻接表表示时具有线性时间复杂度。

17 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
算法有向图强连通分量深度优先搜索伪代码有向无环图邻接表时间复杂度Kosaraju–S…

Kosaraju–Sharir 算法是一种图算法,用于将有向图划分为若干强连通分量,即沿有向边任意两点都能相互到达的极大顶点集合。它执行两遍深度优先搜索(DFS),一遍在原图上进行,另一遍在将所有边反向后得到的图上进行。第一遍确定的顺序保证了第二遍中的每棵搜索树恰好识别出一个强连通分量。对于用邻接表表示的图,该算法的运行时间为 O(∣V∣+∣E∣)O(|V|+|E|)。

问题与术语

设 G=(V,E)G=(V,E) 是一个有限有向图,其中 VV 为顶点集,EE 为边集。当以下两个条件同时成立时,顶点 uu 和 vv 属于同一个强连通分量:

  • 存在从 uu 到 vv 的有向路径。
  • 存在从 vv 到 uu 的有向路径。

这里允许长度为零的路径,因此每个顶点都属于某个分量,孤立顶点也不例外。相互可达是一种等价关系,因此这些分量构成了 VV 的唯一划分。

转置图记作 GTG^{T},其顶点与 GG 相同,但每条边的方向都相反:

GT=(V,ET),ET={(v,u):(u,v)∈E}.G^{T}=(V,E^{T}), \qquad E^{T}=\{(v,u):(u,v)\in E\}.

对图进行转置不会改变其强连通分量:将路径反向只是交换了两个可达性条件,并不改变哪些顶点对同时满足这两个条件。

该算法以 S. Rao Kosaraju 和 Micha Sharir 的名字命名。其核心特点是利用 DFS 的完成顺序来协调两次图遍历。

算法

该算法有两种对称的版本。一种先搜索 GG,再搜索 GTG^{T};另一种先搜索 GTG^{T},再搜索 GG。只要第二遍按第一遍完成时间的降序处理顶点,这两种版本都是正确的。

以下采用先搜索 GG 的版本。

第一遍:记录完成顺序

对 GG 执行完整的 DFS,必要时从任意尚未访问的顶点开始新的搜索。当某个顶点的所有出边都探索完毕时,将该顶点追加到一个列表中。

这样得到的顶点列表按 DFS 完成时间递增排列。逆序读取该列表,就得到完成时间的降序,也称为逆后序。

列表必须记录完成顺序,而不是发现顺序。只有从某个顶点发起的所有递归搜索都返回后,才能将该顶点追加到列表中。

第二遍:收集分量

重置访问状态,然后按完成列表的逆序扫描顶点。每当遇到尚未访问的顶点时,就从它出发,在 GTG^{T} 上进行 DFS。

本次搜索到达的所有此前未访问的顶点,恰好构成一个强连通分量。为这些顶点赋予相同的分量标识符,然后继续扫描列表。

第二遍使用一个全局的访问状态数组或分量标签数组。已经归入先前分量的顶点不会再次被探索。

伪代码

以下伪代码采用递归 DFS,并使用整数作为分量标识符:

KosarajuSharir(G):
    GT = transpose(G)
    visited = 以顶点为索引的数组,初始值均为 false
    finish = 空列表

    procedure FirstDFS(v):
        visited[v] = true
        for each w in G.out_neighbors(v):
            if not visited[w]:
                FirstDFS(w)
        finish.append(v)

    for each vertex v in G:
        if not visited[v]:
            FirstDFS(v)

    component = 以顶点为索引的数组,初始值均为 UNASSIGNED
    count = 0

    procedure SecondDFS(v, id):
        component[v] = id
        for each w in GT.out_neighbors(v):
            if component[w] == UNASSIGNED:
                SecondDFS(w, id)

    for each v in reverse(finish):
        if component[v] == UNASSIGNED:
            SecondDFS(v, count)
            count = count + 1

    return component, count

对于任意两个顶点 uu 和 vv,返回的分量标识符相同,就意味着它们相互可达。标识符的具体数值并不唯一,可能取决于顶点和邻接表的遍历顺序。

正确性原理

缩点图

将每个强连通分量收缩为一个顶点,保留不同分量之间的边。所得的缩点图是一个有向无环图(DAG)。

它不可能包含有向环:如果存在这样的环,环上的各个分量就都能相互到达,因而应当共同构成一个更大的强连通分量。

实际上,该算法利用完成时间,将这些代表分量的顶点排成一个拓扑序,而不必事先知道各个分量。

完成时间的性质

设 f(v)f(v) 为顶点 vv 在第一遍 DFS 中的完成时间。对于分量 CC,定义

F(C)=max⁡v∈Cf(v).F(C)=\max_{v\in C} f(v).

如果存在一条从分量 CC 指向另一分量 DD 的边,那么

F(C)>F(D).F(C)>F(D).

要理解其中的原因,可以分情况考虑哪个分量先被发现:

  • 如果先发现 CC,从中发起的 DFS 就能到达 CC 的所有顶点,并通过分量间的边到达 DD 的所有顶点。这些顶点都会在 CC 中最先被发现的顶点所对应的 DFS 调用结束之前完成搜索。
  • 如果先发现 DD,从中发起的搜索就无法到达 CC,否则从 CC 到 DD 的边加上一条返回路径,会使它们属于同一个分量。因此,对 DD 的搜索会在发现 CC 之前完成。

所以,沿着不同分量之间的每一条边,各分量的最大完成时间都严格递减。

为什么第二遍的每次搜索恰好找到一个分量

在所有尚未分配分量的顶点中,完成时间最大的顶点所在的分量,在 GG 中不可能有来自其他未分配分量的入边。否则,这条入边就会与上述完成时间不等式矛盾。

转置后,该分量便没有指向其他未分配分量的出边。因此,在 GTG^{T} 上进行的搜索不可能从它进入另一个未分配分量。同时,转置保持强连通性,所以搜索能够到达该分量内的每一个顶点。

标记该分量后,同样的论证也适用于其余尚未分配的分量。重复这一过程,就能得到完整的划分。

这一论证并不意味着,一个分量中的每个顶点都比另一个分量中的每个顶点更早完成。提供所需顺序的是各分量的最大完成时间。

示例

考虑一个包含以下边的图:

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

它的强连通分量为

{a,b},{c,d},{e}.\{a,b\},\qquad \{c,d\},\qquad \{e\}.

缩点图是一条链:

{a,b}⟶{c,d}⟶{e}.\{a,b\}\longrightarrow\{c,d\}\longrightarrow\{e\}.

第一遍 DFS 从 aa 开始,按上述边所示的顺序探索邻接顶点,可以得到如下完成列表:

[e,d,c,b,a].[e,d,c,b,a].

第二遍逆序读取该列表,并在转置图上进行搜索:

  1. 从 aa 开始,到达 aa 和 bb。
  2. 从下一个尚未分配分量的顶点 cc 开始,到达 cc 和 dd。指向已经分配的分量的边均被忽略。
  3. 从 ee 开始,只收集到 ee。

采用这样的两遍搜索方向时,分量按原图缩点图的拓扑序被发现。如果先搜索 GTG^{T},再搜索 GG,得到的分量顺序则相反。

复杂度与实现

采用邻接表表示时,构建转置图需要 O(∣V∣+∣E∣)O(|V|+|E|) 时间。每一遍 DFS 都恰好访问每个顶点一次、检查每条边一次。因此,总体时间复杂度为

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

辅助空间复杂度取决于图的存储方式:

  • 访问状态、分量标签、完成列表和 DFS 栈共需 O(∣V∣)O(|V|) 空间。
  • 单独构建并存储转置图需要 O(∣V∣+∣E∣)O(|V|+|E|) 额外空间。
  • 如果已有入边和出边的邻接表,或者能够使用反向视图,那么除图本身的存储空间外,遍历仅需 O(∣V∣)O(|V|) 辅助空间。

若使用邻接矩阵表示,枚举邻接顶点通常会使运行时间达到 O(∣V∣2)O(|V|^2)。

递归与迭代实现

递归实现比较简洁,但 DFS 树的深度可能达到 ∣V∣|V|。对于规模较大或形似长路径的图,这可能超出可用的调用栈容量。

迭代实现可以使用显式的栈。第一遍必须保持真正的 DFS 完成顺序,通常做法是用栈帧保存顶点及其下一个尚未探索的邻接顶点,或显式记录进入和退出事件。仅在顶点第一次入栈时记录它们,无法得到所需的顺序。

第二遍只关心尚未分配分量的顶点所构成的子图中的可达性。因此,可以用广度优先搜索替代 DFS,而不改变最终得到的分量。

常见实现错误

典型错误包括:

  • 记录发现顺序,而非完成顺序。
  • 正序而非逆序读取完成列表。
  • 两遍搜索使用相同的边方向。
  • 两遍搜索之间没有重置访问状态。
  • 第一遍只从一个顶点开始,导致不可达区域未被处理。
  • 在第二遍中,每处理完一个分量就清空访问状态,导致已分配的顶点再次被收集。

自环和平行边不需要为保证正确性而进行特殊处理,不过平行边会增加检查边的次数。

应用与相关算法

强连通分量能够揭示有向系统中相互依赖的部分。其应用包括在编译器中对递归依赖关系进行分组、在模型检测中组织状态图,以及将图化为无环的缩点图以供后续处理。分量标签可以直接回答两个顶点是否相互可达,但仅凭这些标签无法回答任意的单向可达性查询。

该算法还可以通过蕴含图求解二元可满足性问题:当且仅当某个变量及其否定属于同一个强连通分量时,公式不可满足。

Tarjan 强连通分量算法利用一遍 DFS、一个活动顶点栈和 low-link 值,在 O(∣V∣+∣E∣)O(|V|+|E|) 时间内解决同一问题。与标准的 Kosaraju–Sharir 实现不同,它不需要单独的转置图。而两遍搜索的方法则将确定顺序与提取分量这两个步骤清晰地分开。

Kosaraju–Sharir 是一种静态图算法,即为一个固定的图计算强连通分量。若要在插入或删除边时高效维护分量,就需要使用动态算法,而不能仅仅保留原有的完成顺序。