Kosaraju算法求有向图的强连通分量 题目描述 给定一个有向图 \( G = (V, E) \)，其强连通分量（SCC）是最大的顶点子集，其中任意两个顶点 \( u \) 和 \( v \) 均相互可达（即存在从 \( u \) 到 \( v \) 和从 \( v \) 到 \( u \) 的路径）。Kosaraju算法旨在找出图 \( G \) 的所有强连通分量。要求设计一个高效算法，并解释其步骤。 解题过程 算法核心思想 Kosaraju算法基于以下关键观察： 步骤1：对原图 \( G \) 进行深度优先搜索（DFS），记录顶点的完成时间（即DFS回溯的顺序）。 步骤2：构造原图 \( G \) 的转置图 \( G^T \)（即将所有边反向）。 步骤3：按照完成时间从晚到早的顺序（即步骤1的逆序），对转置图 \( G^T \) 进行DFS。每次DFS遍历到的顶点构成一个强连通分量。 原理：在转置图中，SCC的内部结构不变，但SCC之间的边反向。按完成时间逆序遍历，可确保从"源SCC"（在转置图中无入边）开始，逐步剥离SCC。 详细步骤 (1) 第一次DFS：记录完成顺序 初始化访问数组 visited[] ，全部设为 false 。 初始化栈 stack ，用于记录顶点完成顺序（后进先出）。 对每个未访问顶点执行DFS： 标记顶点为已访问。 递归访问其未访问的邻居。 将该顶点压入栈（在递归结束后）。 示例：对图 \( G \) 的顶点依次DFS，完成后栈顶为完成时间最晚的顶点。 (2) 构建转置图 \( G^T \) 创建新图 \( G^T \)，遍历原图 \( G \) 的每条边 \( (u, v) \)，在 \( G^T \) 中添加边 \( (v, u) \)。 时间复杂度：\( O(|V| + |E|) \)。 (3) 第二次DFS：按逆序遍历 \( G^T \) 重置 visited[] 为全 false 。 依次弹出栈顶顶点： 若顶点未访问，以其为起点对 \( G^T \) 执行DFS，本次DFS访问的所有顶点属于同一个SCC。 记录该SCC（如存入列表）。 示例：从栈中弹出完成时间最晚的顶点，在 \( G^T \) 中DFS，得到的连通区域即为一个SCC。 实例演示 考虑有向图 \( G \) 的顶点集 \( V = \{0,1,2,3,4\} \)，边集 \( E = \{(1,0), (0,2), (2,1), (0,3), (3,4)\} \)。 步骤1 ：对 \( G \) 做DFS（从顶点0开始）： 遍历顺序：0→2→1（完成顺序：1, 2, 0），然后0→3→4（完成顺序：4, 3, 0）。 栈内容（从顶到底）：[ 1,2,4,3,0 ]（完成时间递增）。 步骤2 ：构建 \( G^T \)，边反向为 \( \{(0,1), (2,0), (1,2), (3,0), (4,3)\} \)。 步骤3 ：按栈顺序 [ 0,3,4,2,1 ] 遍历 \( G^T \)： 弹出0：在 \( G^T \) 中DFS从0出发，访问 {0,1,2}，得SCC1。 弹出3：未访问，DFS访问 {3}，得SCC2。 弹出4：未访问，DFS访问 {4}，得SCC3。 结果：SCC为 {0,1,2}, {3}, {4}。 算法复杂度 时间复杂度：两次DFS和构建转置图均为 \( O(|V| + |E|) \)。 空间复杂度：\( O(|V|) \)（存储栈、访问数组和递归栈）。 关键点说明 第一次DFS的目的是确定拓扑顺序（尽管图可能有环，但完成时间逆序近似于拓扑排序）。 转置图确保在第二次DFS时，从SCC的"源点"开始，避免跨SCC遍历。 算法正确性依赖于：SCC在转置图中不变，且逆序遍历能优先访问"汇SCC"（在 \( G^T \) 中为源）。