Kosaraju-Sharir算法求有向图的强连通分量 题目描述 给定一个有向图 \( G = (V, E) \)，要求找出其所有强连通分量（Strongly Connected Component, SCC）。强连通分量是图的一个极大子图，其中任意两个顶点 \( u \) 和 \( v \) 均相互可达（即存在从 \( u \) 到 \( v \) 的路径，也存在从 \( v \) 到 \( u \) 的路径）。Kosaraju-Sharir 算法通过两次深度优先搜索（DFS）高效解决该问题，时间复杂度为 \( O(|V| + |E|) \)。 解题步骤 1. 算法核心思想 关键观察 ：将原图 \( G \) 的边反向得到转置图 \( G^T \)，则 \( G \) 和 \( G^T \) 的强连通分量完全相同。 策略 ： 在 \( G \) 上执行 DFS，记录顶点的完成时间（即递归栈返回的顺序）。 根据完成时间降序，在 \( G^T \) 上执行 DFS，每次 DFS 遍历到的顶点构成一个强连通分量。 2. 步骤详解 步骤 1：第一次 DFS（在原图 \( G \) 上） 对原图 \( G \) 执行深度优先搜索，遍历所有未访问顶点。 在递归回溯时，将顶点压入栈（或记录其完成顺序）。 注意 ：此处栈仅用于记录顶点完成顺序，不参与强连通分量的划分。 示例 ： 假设图 \( G \) 有顶点 \( \{A, B, C, D, E\} \)，边为 \( A \to B, B \to C, C \to A, B \to D, D \to E \)。 DFS 可能顺序：从 \( A \) 开始，访问 \( B \)，再访问 \( C \)（回溯至 \( B \)），访问 \( D \)，最后访问 \( E \)。 完成时间栈（从早到晚）：\( [ E, D, C, B, A ] \)（实际顺序可能因起点和邻接顺序而异）。 步骤 2：构建转置图 \( G^T \) 将 \( G \) 中所有边的方向反转，得到 \( G^T \)。 示例 ： 原边 \( A \to B, B \to C, C \to A, B \to D, D \to E \) 变为： \( B \to A, C \to B, A \to C, D \to B, E \to D \)。 步骤 3：第二次 DFS（在 \( G^T \) 上） 按照步骤 1 中栈的弹出顺序（即完成时间降序）依次处理顶点。 对每个未访问顶点，在 \( G^T \) 上执行 DFS，本次 DFS 访问到的所有顶点属于同一个强连通分量。 示例 ： 栈顶顺序为 \( A \)（最早完成）→ \( B \) → \( C \) → \( D \) → \( E \)。 从 \( A \) 开始：在 \( G^T \) 中，\( A \to C \to B \to A \)，访问 \( \{A, B, C\} \) 为一个 SCC。 下一个未访问顶点 \( D \)：在 \( G^T \) 中，\( D \to B \) 但 \( B \) 已访问，故仅 \( \{D\} \) 为一个 SCC。 最后 \( E \)：在 \( G^T \) 中，\( E \to D \) 但 \( D \) 已访问，故 \( \{E\} \) 为一个 SCC。 强连通分量结果为：\( \{A, B, C\}, \{D\}, \{E\} \)。 3. 正确性解释 第一次 DFS 的完成顺序保证了在 \( G^T \) 中，优先从“源 SCC”（即无出边的 SCC）开始搜索。 在 \( G^T \) 中，从源 SCC 出发的 DFS 不会进入其他 SCC，因为 \( G^T \) 的边方向与原图相反。 4. 复杂度分析 两次 DFS 的时间均为 \( O(|V| + |E|) \)。 构建 \( G^T \) 需遍历所有边，时间复杂度 \( O(|E|) \)。 总复杂度：\( O(|V| + |E|) \)，适用于大规模稀疏图。 5. 应用场景 代码依赖分析（如模块间的循环依赖检测）。 社交网络中社区发现。 编译器中的死代码消除。