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

Kosaraju 算法

Kosaraju 算法通过两次图遍历和边的反向,在线性时间内求出有向图的强连通分量。

19 个关键词1 个词条链接到这里5 个尚未撰写AI 撰写
有向图强连通分量算法深度优先搜索邻接表有向无环图广度优先搜索伪代码Kosaraju…

Kosaraju 算法是一种用于求解有向图的强连通分量的算法。它执行两次图遍历:第一次根据深度优先搜索的完成时间确定顶点顺序,第二次则在所有边均已反向的图上进行搜索。采用邻接表表示图时,其运行时间为 O(∣V∣+∣E∣)O(|V|+|E|),其中 VV 是顶点集,EE 是边集。该算法也称为 Kosaraju–Sharir 算法,这一名称体现了其归功于 S. Rao Kosaraju 和 Micha Sharir。

问题与定义

在有向图 G=(V,E)G=(V,E) 中,如果既存在从 uu 到 vv 的有向路径,也存在从 vv 到 uu 的有向路径,则称顶点 uu 和 vv 相互可达。相互可达关系将顶点划分为若干强连通分量,通常缩写为 SCC。

每个强连通分量都是极大的:无法再加入任何顶点,同时仍保持分量内所有顶点之间相互可达。每个顶点恰好属于一个强连通分量。即使没有自环,单个顶点也可以构成一个强连通分量,因为长度为零的路径将该顶点与自身相连。

以下两种相关的图构造有助于解释该算法:

  • 转置图 GTG^{T} 与 GG 具有相同的顶点,但将每条边 (u,v)(u,v) 替换为 (v,u)(v,u)。将所有边反向不会改变强连通分量。
  • **凝聚图**将每个强连通分量替换为一个顶点,并保留不同分量之间的边。它是一个有向无环图:如果不同分量之间存在环,这些分量就会相互可达,因而实际上应当属于同一个分量。

目标是为每个顶点分配一个分量标识符,或者等价地,输出构成各个强连通分量的顶点集合。

算法

一种标准版本先搜索 GG,再搜索 GTG^{T}。

第一遍:记录完成顺序

对整个原图执行深度优先搜索。每当搜索完成对某个顶点的处理,即检查完它的所有出邻居后,就将该顶点追加到一个列表中。

外层搜索必须遍历所有顶点,每当遇到尚未访问的顶点时,就启动一次新的深度优先搜索。从任意起点出发的单次深度优先搜索不一定能到达整个图的所有顶点。

在顶点处理完成时将其追加到列表中,得到的是按完成时间递增排列的顺序。反向读取该列表,就得到按完成时间递减排列的顺序,通常称为逆后序。

将图反向

构造 GTG^{T},或者提供访问每个顶点入邻居的方式。

这一步也可以在第一遍遍历之前完成;关键只在于每次遍历所使用的边方向。

第二遍:提取分量

清除访问状态。按照第一遍完成时间递减的顺序考察顶点。每当遇到尚未访问的顶点时,就从该顶点出发,在 GTG^{T} 中启动搜索,且只访问尚未被分配到任何分量的顶点。

这次搜索中新到达的所有顶点构成一个强连通分量。为它们分配相同的分量标识符,然后继续按上述顺序处理。

第二遍遍历通常也采用深度优先搜索,但使用广度优先搜索同样可行:对完成时间的要求只适用于第一遍,第二遍只需收集所有可达且尚未分配的顶点。

伪代码

以下伪代码在两遍遍历中都使用递归式深度优先搜索:

kosaraju(G):
    visited = 空集合
    finish_order = 空列表

    visit_first(v):
        将 v 加入 visited
        对 outgoing_neighbors(G, v) 中的每个 w:
            如果 w 不在 visited 中:
                visit_first(w)
        将 v 追加到 finish_order

    对 G 中的每个顶点 v:
        如果 v 不在 visited 中:
            visit_first(v)

    GT = transpose(G)
    component = 空映射
    component_count = 0

    visit_second(v, id):
        component[v] = id
        对 outgoing_neighbors(GT, v) 中的每个 w:
            如果 w 不在 component 中:
                visit_second(w, id)

    按逆序遍历 finish_order 中的每个 v:
        如果 v 不在 component 中:
            visit_second(v, component_count)
            component_count = component_count + 1

    返回 component

一种对称的变体先搜索 GTG^{T},然后按照第一遍完成时间递减的顺序搜索 GG。这两种变体都是正确的,但必须保证各遍遍历使用的边方向与处理顺序相互匹配。

正确性原理

关键性质涉及的是整个分量的完成时间,而不一定是不同分量中每一对顶点的相对完成时间。

设 f(v)f(v) 为顶点 vv 在第一遍深度优先搜索中的完成时间。对于分量 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,深度优先搜索能够到达 CC 中的所有顶点,并进一步到达 DD。只有在 DD 中所有顶点都完成后,CC 中最先被发现的顶点才会完成。
  • 如果先发现 DD,从 DD 出发的深度优先搜索就不可能到达 CC。否则,加上从 CC 到 DD 的边,这两个分量就会相互可达。因此,在发现 CC 之前,DD 中的所有顶点都已完成。

因此,按 F(C)F(C) 递减排列,就得到了原图凝聚图的一个拓扑排序。

第二遍遍历首先处理的分量,在原图中没有来自任何尚未分配分量的入边。因此,在转置图中,它也没有通向其他尚未分配分量的出边。从该分量出发的搜索:

  1. 能够到达该分量内的每个顶点,因为将边反向不会破坏强连通性;
  2. 无法进入另一个尚未分配的分量。

因此,这次搜索恰好提取出一个强连通分量。每提取一个分量后,再应用同样的论证,即可证明算法对整个图都正确。

对于先搜索 GG 的版本,分量按照原图凝聚图的一个拓扑序输出。如果先搜索 GTG^{T},则得到方向相反的分量顺序。

示例

考虑一个具有以下边的图:

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

它的强连通分量为

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

这些分量构成的凝聚图是一条链:

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

假设第一遍深度优先搜索从 aa 开始,沿着这条链上的边一直搜索,然后再回溯。一种可能的完成顺序列表为

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

因此,第二遍按以下顺序考察顶点:

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

在转置图中,从 aa 出发的搜索恰好到达 {a,b,c}\{a,b,c\}。下一个尚未分配的起始顶点是 dd,从它出发得到 {d,e}\{d,e\}。最后,ff 单独构成一个分量。

以不同顺序遍历顶点和邻居,可能改变完成顺序列表以及分量的数字标签,但不会改变强连通分量的划分。

复杂度与实现

使用邻接表时,每次深度优先搜索对每个顶点和每条边的检查次数至多为常数。构造转置图也只需线性时间。因此,总体时间复杂度为

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

空间复杂度取决于图的表示方式,以及将哪些存储计入其中:

  • 访问标记、分量标签、完成顺序列表和遍历状态需要 O(∣V∣)O(|V|) 的辅助空间。
  • 显式存储转置图还需要 O(∣V∣+∣E∣)O(|V|+|E|) 的空间。
  • 如果已经同时保存了入边和出边的邻接表,算法就可以直接使用,无需另行创建转置图。

如果使用邻接矩阵并直接逐行扫描,运行时间为 O(∣V∣2)O(|V|^2),而不是与边数成线性关系。

迭代式深度优先搜索

递归实现所需的递归深度可能与 ∣V∣|V| 成正比,在路径很长时可能耗尽调用栈空间。迭代实现可以使用显式的栈,但必须保留第一遍深度优先搜索中的完成事件。

仅在顶点首次入栈或被发现时记录它们是不够的。常见实现会使用栈帧保存下一个待检查的邻居,或者将进入事件和退出事件分开处理。只有处理完一个顶点的所有后代后,才将该顶点追加到完成顺序列表中。

其他实现注意事项

  • 第一遍必须覆盖所有顶点,包括孤立顶点。
  • 第二遍必须重新初始化访问状态,或者使用初始为空的分量分配映射。
  • 自环和平行边不会影响正确性。
  • 分量标识符只是标签,并不是图的固有属性。
  • 空图不产生任何分量。
  • 通常的实现假定图在两遍遍历期间保持不变;它并不是一种在图更新时维护强连通分量的增量算法。

应用与相关算法

强连通分量分解将有向图中存在环的区域与这些区域之间的无环关系分离开来。其应用包括:

  • **依赖分析:**可以先将相互依赖的模块、任务或定义归为一组,再处理它们的凝聚图。
  • 程序分析:编译器和静态分析系统可以识别控制流图或依赖图中存在环的区域,以便进行迭代处理。
  • **有向可达性:**将强连通分量收缩后,可将可达性问题转化为一个更小的无环图上的问题;不过,要高效回答任意可达性查询,仍需进一步处理。
  • **二元可满足性问题:**一个 2-CNF 布尔公式不可满足,当且仅当某个变量及其否定在该公式的蕴含图中属于同一个强连通分量。

Kosaraju 算法将完成顺序的计算与分量提取分开,因此特别易于解释和验证。它在实际应用中的主要开销是需要沿两个方向遍历边。

Tarjan 强连通分量算法同样具有 O(∣V∣+∣E∣)O(|V|+|E|) 的运行时间,但它利用发现序号、低链接值和一个栈,在一次深度优先搜索中识别各个分量,无需构造转置图。这两种算法得到的强连通分量划分相同,但在遍历状态的维护、内存需求以及分量输出顺序方面有所不同。