图的强连通分支与Kosaraju算法 1. 基础概念回顾 有向图 ：由顶点集V和边集E构成，每条边是有方向的（从起点指向终点）。 强连通性 ：在有向图G中，若任意两个顶点u和v之间存在双向路径（u→v和v→u），则称G是强连通的。 强连通分支 ：有向图的极大强连通子图。每个顶点属于且仅属于一个强连通分支。 2. 强连通分支的性质 分支图是DAG ：若将每个强连通分支收缩为单个顶点，得到的新图（称为分支图或凝聚图）是有向无环图。 应用场景 ：用于编译器优化（循环检测）、社交网络分析（社群发现）、数据依赖分析等。 3. Kosaraju算法的核心思想 关键观察 ：强连通分支在图的转置（边反向）中保持不变。 两步流程 ： 第一次DFS ：在原图G上执行深度优先搜索，按完成时间递减的顺序记录顶点。 第二次DFS ：在转置图G^T上，按第一次DFS的记录顺序进行DFS，每次DFS遍历的顶点构成一个强连通分支。 4. 算法步骤详解 步骤1：计算完成时间 对原图G执行DFS，记录每个顶点的完成时间（即递归栈弹出的顺序）。 例如：顶点A在DFS中最后完成，则其完成时间最晚。 步骤2：转置图构建 将G的所有边反向，得到G^T。 步骤3：按完成时间逆序搜索 在G^T上，按完成时间从晚到早的顺序对未访问顶点执行DFS。 每次DFS访问的顶点集合即为一个强连通分支。 5. 正确性证明思路 引理 ：若两个顶点u和v属于同一强连通分支，则在G^T中，从u出发能到达v，且从v出发能到达u。 分支图DAG性质 ：由于分支图是无环的，按完成时间逆序搜索可确保先处理分支图中的"源"分支（无入边的分支），避免跨分支污染。 6. 时间复杂度分析 DFS的时间复杂度为O(|V|+|E|)。 转置图构建需O(|E|)时间。 总复杂度为O(|V|+|E|)，适用于大规模稀疏图。 7. 示例演示 考虑有向图G：顶点集{A,B,C,D}，边集{A→B, B→C, C→A, B→D}。 第一次DFS ：从A开始，遍历顺序A→B→C→D，完成时间顺序为D、C、B、A。 转置图G^T ：边变为{B→A, C→B, A→C, D→B}。 第二次DFS ：按完成时间逆序（A、B、C、D）在G^T上搜索： 从A开始可访问{A,C,B}（分支1）， 剩余D单独成分支（分支2）。 8. 对比其他算法 Tarjan算法 ：通过单次DFS和lowlink值实时追踪分支，节省空间但实现复杂。 Gabow算法 ：类似Tarjan，但用双栈替代lowlink数组，提高稳定性。 Kosaraju的优势在于逻辑清晰，易于并行化（如并行DFS）。