Kosaraju算法核心原理疑问及示例执行错误求解

你的问题出在两个关键操作上：

1. 首次DFS的栈压入顺序完全搞反了
2. 第二步DFS误用了原图，而非算法要求的转置图（所有边方向反转后的图）

正确执行步骤（以A→B的图为例） #

第一步：原图DFS，按完成时间压栈

Kosaraju的栈规则是节点完成所有子节点遍历后才压入，不是访问时就压：

• 从A出发，标记A为已访问，遍历其邻居B
• 标记B为已访问，B没有出边，完成遍历，将B压入栈 → 栈内容：[B]
• 回到A，A的所有子节点处理完毕，完成遍历，将A压入栈 → 栈内容：[B, A]（栈顶是A，弹出顺序为A先、B后）

第二步：构建转置图

将原图所有边反转：原图是A→B，转置图的边为B→A（转置图的强连通分量和原图完全一致，这是算法的核心前提）

第三步：转置图DFS（按栈弹出顺序）

• 弹出A，A未被访问，以A为起点在转置图中DFS：A没有出边，得到强连通分量{A}，标记A为已访问
• 弹出B，B未被访问，以B为起点在转置图中DFS：B的出边指向A，但A已被访问，得到强连通分量{B}，标记B为已访问

最终得到的两个独立强连通分量和预期一致。

你的错误细节 #

• 你把首次DFS的栈顺序搞成了[A,B]，这是混淆了“访问节点”和“完成节点遍历”的时机，正确栈的弹出顺序应该是完成时间最晚的节点先出。
• 第二步你用原图做DFS，错误地认为A指向B就该把A归入B的分量——但算法第二步必须用转置图，转置图中B的遍历无法触及未被访问的A（因为A已经先被处理标记），自然不会出现错误合并的情况。

内容的提问来源于stack exchange，提问作者Ferran Espuña