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

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

什么是强连通分量?

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

环境要求

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

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

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

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

基础概念

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

有向图与强连通性

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

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

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

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

逆图(Transpose Graph)

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

缩点(Condensation)与 DAG

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

3. Kosaraju 算法详解

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

算法步骤

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

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

构建逆图

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

第二次 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) // 在递归返回时记录节点 示例演示

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

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

构建逆图: 所有边反转.

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

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