算法引入
在有向图分析中，强连通分量（Strongly Connected Component, SCC） 是指图中任意两个顶点互相可达的最大子图。SCC分解是图论中最基础的操作之一，广泛应用于社交网络社区发现、编译器控制流分析、网页链接结构挖掘等领域。Kosaraju算法由S. Rao Kosaraju于1978年提出，是求解SCC最直观的方法之一。它基于两次深度优先搜索（DFS），第一次确定顶点完成时间的逆序，第二次在转置图上按该逆序进行DFS，每次DFS遍历到的顶点即为一个SCC。
核心思想
Kosaraju算法的核心洞察来源于以下定理：原图和转置图（所有边反向）具有完全相同的强连通分量集合。算法分两步执行：
第一步：确定处理顺序
在原图上执行DFS，记录每个顶点的完成时间（finish time），将顶点按完成时间从大到小排序。这个顺序保证：如果存在从SCC A到SCC B的边，则A中的顶点完成时间一定晚于B中的顶点。
第二步：在转置图上DFS
按第一步得到的逆序，在转置图上依次对每个未访问顶点执行DFS。每次DFS所到达的所有顶点构成一个强连通分量。
Java完整实现
import java.util.*;
/**
* Kosaraju强连通分量分解算法
* 两次DFS实现有向图的SCC缩点
*/
public class KosarajuSCC {
private final int n; // 顶点数量
private final List<List<Integer>> adj; // 原图邻接表
private final List<List<Integer>> radj; // 转置图邻接表
private boolean[] visited;
private final Deque<Integer> finishStack; // 第一次DFS的完成顺序栈
private List<List<Integer>> sccs; // 所有强连通分量
private int[] componentId; // 每个顶点所属的SCC编号
private int sccCount; // SCC总数
public KosarajuSCC(int n) {
this.n = n;
this.adj = new ArrayList<>();
this.radj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
radj.add(new ArrayList<>());
}
this.finishStack = new ArrayDeque<>();
this.componentId = new int[n];
Arrays.fill(componentId, -1);
}
/**
* 添加有向边
* @param u 起点
* @param v 终点
*/
public void addEdge(int u, int v) {
adj.get(u).add(v);
radj.get(v).add(u); // 同时构建转置图的边
}
/**
* 执行Kosaraju算法，分解所有强连通分量
*/
public void findSCCs() {
// 第一步：在原图上DFS，记录完成顺序
visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfsFirst(i);
}
}
// 第二步：在转置图上按逆序DFS
visited = new boolean[n];
sccs = new ArrayList<>();
sccCount = 0;
while (!finishStack.isEmpty()) {
int v = finishStack.pop();
if (!visited[v]) {
List<Integer> scc = new ArrayList<>();
dfsSecond(v, scc);
sccs.add(scc);
for (int node : scc) {
componentId[node] = sccCount;
}
sccCount++;
}
}
}
/**
* 第一次DFS：在原图上遍历，将顶点按完成时间入栈
*/
private void dfsFirst(int u) {
visited[u] = true;
for (int v : adj.get(u)) {
if (!visited[v]) {
dfsFirst(v);
}
}
finishStack.push(u); // 完成时入栈
}
/**
* 第二次DFS：在转置图上遍历，收集一个SCC的所有顶点
*/
private void dfsSecond(int u, List<Integer> scc) {
visited[u] = true;
scc.add(u);
for (int v : radj.get(u)) {
if (!visited[v]) {
dfsSecond(v, scc);
}
}
}
/**
* 获取所有强连通分量
*/
public List<List<Integer>> getSCCs() {
return sccs;
}
/**
* 获取强连通分量数量
*/
public int getSCCCount() {
return sccCount;
}
/**
* 获取顶点所属的SCC编号
*/
public int getComponentId(int v) {
return componentId[v];
}
/**
* 构建缩点后的DAG（有向无环图）
* 每个SCC作为一个超级节点
*/
public KosarajuSCC buildCondensationGraph() {
KosarajuSCC dag = new KosarajuSCC(sccCount);
boolean[][] added = new boolean[sccCount][sccCount];
for (int u = 0; u < n; u++) {
int cu = componentId[u];
for (int v : adj.get(u)) {
int cv = componentId[v];
if (cu != cv && !added[cu][cv]) {
dag.addEdge(cu, cv);
added[cu][cv] = true;
}
}
}
return dag;
}
/**
* 判断两个顶点是否在同一个强连通分量中
*/
public boolean inSameSCC(int u, int v) {
return componentId[u] == componentId[v];
}
/**
* 打印SCC分解结果
*/
public void printSCCs() {
System.out.println("强连通分量分解结果（共 " + sccCount + " 个SCC）：");
for (int i = 0; i < sccs.size(); i++) {
List<Integer> scc = sccs.get(i);
System.out.println(" SCC " + i + ": " + scc);
}
}
/**
* 打印缩点后的DAG结构
*/
public void printCondensationDAG() {
KosarajuSCC dag = buildCondensationGraph();
System.out.println("\n缩点后的DAG（" + sccCount + " 个超级节点）：");
for (int i = 0; i < sccCount; i++) {
System.out.println(" 超级节点 " + i + " -> " + dag.adj.get(i));
}
}
/**
* 查找包含指定顶点的SCC大小
*/
public int getSCCSize(int v) {
int cid = componentId[v];
int size = 0;
for (int id : componentId) {
if (id == cid) size++;
}
return size;
}
/**
* 获取最大的强连通分量
*/
public List<Integer> getLargestSCC() {
List<Integer> largest = new ArrayList<>();
for (List<Integer> scc : sccs) {
if (scc.size() > largest.size()) {
largest = scc;
}
}
return largest;
}
public static void main(String[] args) {
// 构造示例有向图
// 0 -> 1 -> 2 -> 0 (SCC: {0,1,2})
// 1 -> 3
// 3 -> 4 -> 5 -> 3 (SCC: {3,4,5})
// 6 -> 7 (SCC: {6}, {7})
KosarajuSCC graph = new KosarajuSCC(8);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(1, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 5);
graph.addEdge(5, 3);
graph.addEdge(6, 7);
graph.findSCCs();
graph.printSCCs();
System.out.println("\n连通性查询:");
System.out.println(" 0和2在同一SCC: " + graph.inSameSCC(0, 2));
System.out.println(" 0和3在同一SCC: " + graph.inSameSCC(0, 3));
System.out.println(" 3和5在同一SCC: " + graph.inSameSCC(3, 5));
System.out.println(" SCC 0 的大小: " + graph.getSCCSize(0));
graph.printCondensationDAG();
// 社交网络应用：找出最大的社区
System.out.println("\n最大社区(SCC): " + graph.getLargestSCC());
// 更复杂的示例：2-SAT问题中的蕴含图
System.out.println("\n=== 2-SAT蕴含图示例 ===");
KosarajuSCC satGraph = new KosarajuSCC(6); // 3个变量，每个有正/负两种文字
// 子句 (x0 || x1) 转化为 ~x0 -> x1 和 ~x1 -> x0
// 子句 (~x0 || x2) 转化为 x0 -> x2 和 ~x2 -> ~x0
// 文字编号：x_i = 2*i, ~x_i = 2*i+1
satGraph.addEdge(1, 2); // ~x0 -> x1
satGraph.addEdge(3, 0); // ~x1 -> x0
satGraph.addEdge(0, 4); // x0 -> x2
satGraph.addEdge(5, 1); // ~x2 -> ~x0
satGraph.findSCCs();
satGraph.printSCCs();
// 检查是否可满足：不存在 x_i 和 ~x_i 在同一SCC中
boolean satisfiable = true;
for (int i = 0; i < 3; i++) {
if (satGraph.inSameSCC(2*i, 2*i+1)) {
System.out.println("变量 x" + i + " 与其否定在同一SCC，公式不可满足");
satisfiable = false;
}
}
System.out.println("公式可满足: " + satisfiable);
}
}
算法对比与扩展
Kosaraju vs Tarjan vs Gabow
| 算法 | 遍历次数 | 额外空间 | 特点 |
|---|---|---|---|
| Kosaraju | 2次DFS | O(V) | 直观易懂，需要构建转置图 |
| Tarjan | 1次DFS | O(V) | 单遍扫描，lowlink数组，最常用 |
| Gabow | 1次DFS | O(V) | 使用两个栈维护路径信息 |
Kosaraju的优势在于逻辑清晰，代码简洁；劣势是需要存储转置图。在内存受限的场景下，Tarjan算法更优。
缩点DAG的应用
将每个SCC收缩为超级节点后，得到的有向无环图（DAG）可用于：
- 拓扑排序：按DAG的拓扑序处理各SCC
- 关键路径分析：在DAG上求最长路径
- 动态规划：按逆拓扑序进行状态转移
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V + E) | 两次DFS各线性时间 |
| 空间复杂度 | O(V + E) | 原图+转置图+访问标记 |
| 缩点建图 | O(V + E) | 遍历所有边判断跨SCC边 |
应用场景
Kosaraju算法及其SCC分解在以下场景有广泛应用：
- 社交网络分析：发现紧密互动的社区群体，识别影响力核心
- 编译器优化：控制流图中识别循环结构，进行代码优化
- 网页链接分析：将互相引用的网页组识别为”链接农场”
- 2-SAT问题求解：判断布尔公式可满足性的关键步骤
- 电路设计：分析数字电路中的反馈环路
- 依赖管理：软件包依赖图中识别循环依赖
Kosaraju算法以简洁的两遍DFS优雅地解决了强连通分量分解问题，是理解有向图结构的基础工具。
