有向图的强连通分量: Kosaraju算法和Tarjan算法详解

在上一篇文章中, 我们了解了图的最小生成树算法. 本节我们来学习 图的强连通分量(Strongly Connected Component, SCC) 算法.

什么是强连通分量?

在 有向图 中, 若一组节点内的任意两个节点都能通过路径互相到达(例如 $A\to B$ 且 $B\to A$), 则这组节点构成一个强连通分量. 它是图中的最大独立连通单元, 可以看作一种对有向图结构的深层划分.

环境要求

本文所用样例在Windows 11以及Ubuntu 24.04上面编译通过.

1. Windows: 使用[Visual Studio],
2. Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本)
3. GCC 无法编译直接本项目代码, 因为本文代码使用了 C++20 Module, 而 GCC 对此支持不完整.

关于 Module 的更多信息, 请参考我之前的博客: CMake 构建 C++20 Module 实例(使用 MSVC)

本项目工程目录: 图论代码

基础概念

在深入算法之前, 我们需要明确几个关键术语和背景知识.

有向图与强连通性

• 强连通性(Strong Connectivity): 若图中任意两节点均能互相到达(即存在 $A\to B$ , $B\to A$的路径), 则该图是强连通的.

  

  上图中任意两点都是强连通的.

• 强连通分量(SCC): 有向图的子集, 其内部节点强连通, 且无法再添加任何其他节点仍保持强连通性(即"最大性").

  

  上图中强连通分量为 {1, 2, 3}

逆图(Transpose Graph)

将原图所有边的方向反转后得到的新图. 例如, 若原图有边 $A\to B$, 逆图中则为: $B\to A$. 在 Kosaraju 算法中, 逆图帮助定位 SCC 的"边界".

缩点(Condensation)与 DAG

缩点操作是将每个 SCC 合并为一个超级节点, 原图中 SCC 间的边简化为超级节点间的边. 缩点后的图无环路, 这一特性在拓扑排序中至关重要. 通过缩点, 复杂图的分析可简化为对 DAG 的操作(例如路径查找或依赖解析).

3. Kosaraju 算法详解

Kosaraju 算法是计算强连通分量(SCC)的高效算法, 时间复杂度为 $O(V+E)$(线性时间). 其核心思想通过两次深度优先搜索(DFS)实现, 结合逆图(Transpose Graph)和栈(Stack)的特性, 逐层剥离 SCC.

算法步骤

1. 第一次 DFS: 标记节点完成顺序

   • 对原图进行深度优先搜索, 按节点完成遍历的逆序将节点压入栈(即最后完成的节点在栈顶).
   • 关键作用: 确保后续处理时, 从"最晚完成"的节点(即潜在 SCC 的"根")开始, 保证 SCC 的完整性.

2. 构建逆图

   • 将原图所有边的方向反转, 生成逆图(Transpose Graph).

3. 第二次 DFS: 提取 SCC

   • 按栈中节点的顺序, 依次从栈顶取出节点, 对逆图进行 DFS.
   • 每轮 DFS 访问的节点构成一个 SCC.

原理剖析

• 为何需要逆图?
  SCC 的强连通性在逆图中保持不变, 但逆图的遍历顺序能天然隔离不同 SCC 的边界.

  • 例如, 原图中存在 A→B, 逆图中则为 B→A. 若 A 和 B 属于同一 SCC, 逆图的 DFS 仍能覆盖两者; 若属于不同 SCC, 逆图的遍历顺序会避免跨分量污染.

• 栈的作用
  第一次 DFS 的逆序栈隐含了原图的拓扑排序(忽略环路), 确保第二次 DFS 从"高层级"分量开始, 避免重复遍历.

伪代码实现

Kosaraju(G):
    // G 是一个有向图

    // Step 1: 对原图G执行深度优先搜索，并记录每个节点的完成时间
    finish_time = [] // 这里我们用一个列表存储按完成时间排序的节点
    visited = [false] * |V| // 初始化所有节点为未访问状态

    for each vertex u in G:
        if not visited[u]:
            DFS(G, u, visited, finish_time)

    // Step 2: 转置图G，得到G^T
    GT = transpose(G)

    // 重置访问标记数组
    visited = [false] * |V|

    // Step 3: 对转置后的图GT执行深度优先搜索，按照原图的完成时间顺序
    while finish_time is not empty:
        v = finish_time.pop() // 取出最后一个元素，即具有最大完成时间的节点
        if not visited[v]:
            // 打印或处理这个强连通分量
            print("SCC:")
            DFS(GT, v, visited) // 注意这里不需要更新finish_time

// 深度优先搜索辅助函数
DFS(graph, start_vertex, visited, finish_time=None):
    visited[start_vertex] = true
    for each neighbor in graph.adjacent(start_vertex):
        if not visited[neighbor]:
            DFS(graph, neighbor, visited, finish_time)
    if finish_time is not None:
        finish_time.append(start_vertex) // 在递归返回时记录节点

示例演示

假设原图如下(边为有向):

1. 第一次 DFS: 假设遍历顺序为 A -> B -> C -> D -> E -> F, 栈中顺序为 栈底[F, E, D, C, B, A]栈顶.

   

2. 构建逆图: 所有边反转.
   

3. 第二次 DFS: 依次弹出栈顶元素处理, 并 DFS 逆图:

   • 从 A 出发, DFS 访问 A -> C -> B, 组成 SCC {A, B, C}.