Kosaraju-Sharir算法求有向图的强连通分量

题目描述
给定一个有向图，其强连通分量（SCC）是一个最大顶点子集，其中任意两个顶点互相可达。Kosaraju-Sharir算法通过两次深度优先搜索（DFS）高效找出所有SCC。该算法的核心思想是利用图的结构性质，避免直接使用Tarjan算法的复杂栈操作。

解题步骤

1. 算法原理

   • 关键观察：将SCC视为超节点后，图变为有向无环图（DAG）。若按拓扑序逆序处理SCC，第二次DFS可逐块捕获SCC。
   • 步骤：
     a. 在原图的反图（所有边反向）上执行DFS，记录顶点完成时间（后序编号）。
     b. 按完成时间降序（即拓扑序逆序）在原图执行DFS，每次DFS遍历的顶点构成一个SCC。

2. 具体实现
   步骤1：构建反图

   • 反图 \(G^T\) 与原图 \(G\) 边方向相反。例如原图边 \(u \to v\)，反图中为 \(v \to u\)。

   步骤2：第一次DFS（在反图上）

   • 对反图执行DFS，遍历结束时将顶点压入栈（或记录后序列表）。这一步目的是获取拓扑序逆序（即若SCC A指向SCC B，则A在栈中位于B之后）。
   • 示例：

     def dfs1(graph, node, visited, stack):  
         visited[node] = True  
         for neighbor in graph[node]:  
             if not visited[neighbor]:  
                 dfs1(graph, neighbor, visited, stack)  
         stack.append(node)  # 完成后入栈  
     

   步骤3：第二次DFS（在原图上，按栈顺序）

   • 从栈顶（最后完成的顶点）开始，在原图执行DFS。每次DFS能访问到的顶点属于同一个SCC，因为反图的拓扑逆序保证了DFS不会跨越SCC边界。
   • 示例：

     def dfs2(graph, node, visited, scc):  
         visited[node] = True  
         scc.append(node)  
         for neighbor in graph[node]:  
             if not visited[neighbor]:  
                 dfs2(graph, neighbor, visited, scc)  
     

3. 完整流程示例

   • 假设有向图：\(0 \to 1 \to 2 \to 0\)（环），外加 \(2 \to 3\)。
   • 反图：\(1 \to 0, 2 \to 1, 0 \to 2, 3 \to 2\)。
   • 第一次DFS（反图）：从0开始遍历顺序可能是0→2→1→3，栈为[1,2,3,0]（具体顺序依赖起点，但SCC {0,1,2}整体在3之后）。
   • 第二次DFS（原图）：按栈顺序[0,3,2,1]处理。从0开始DFS得到SCC {0,1,2}；然后3单独成SCC。

4. 算法正确性解释

   • 反图DFS的栈顺序等价于原图拓扑序的逆序。在第二次DFS时，若先处理SCC A（栈中靠后），则A无法到达尚未访问的SCC B（因B在拓扑序中先于A），从而避免DFS泄漏到其他SCC。

5. 时间复杂度

   • 两次DFS的时间均为 \(O(V+E)\)，空间复杂度 \(O(V)\)。效率优于Tarjan算法常数因子，且实现更简洁。

总结
Kosaraju-Sharir算法通过巧妙的图反转与DFS顺序，将SCC问题转化为两次线性遍历，兼具效率与可读性。其核心在于利用DAG的拓扑性质隔离SCC，确保每次DFS仅探索一个连通分量。