Kosaraju强连通分量查找器

伪代码

两次深度优先搜索加一张转置图。两趟之内都没有任何精巧之处，真正起作用的是第二趟运行时所依据的顺序。

Kosaraju(图):
    // 第一趟：记录完成顺序
    顺序 = []
    对每个未访问的 u: dfs1(u)

    dfs1(u): 标记 u 已访问
             对每条边 (u,v): 若未访问则 dfs1(v)
             顺序.追加(u)            // 在完成时追加

    // 第二趟：在转置图上按完成顺序的逆序做 DFS
    gt = 转置(图)              // 把每条边反向
    对 逆序(顺序) 中的每个 u:
        若 u 未访问:
            在 gt 中从 u 生长出的树就是一个强连通分量

它之所以成立：把所有边反向不会改变强连通分量，因为如果原先能从 x 走到 y 再走回来，反向之后依然可以。反向真正改变的是分量之间那些边的方向。从最后完成的结点开始，可以保证你起步于缩点图的一个源分量；反向之后它原本的出边变成了入边，于是第二趟搜索被困在该分量内部，无法溢出到别的分量去。

分步示例演算

在与 Tarjan 示例完全相同的有向图上运行 Kosaraju，以便直接对照两者。

示例图: 有向边 A 到 B、B 到 C、C 到 A、B 到 D、D 到 E、E 到 D，以及 C 到 F。

1. 第一趟，从 A 开始. 沿 A、B、C 下探；C 到 A 已访问，于是走 C 到 F。F 没有出边，最先完成。接着 C 完成，搜索回到 B 并走 B 到 D，再走 D 到 E；由于 E 到 D 已访问，E 完成，随后 D 完成，再是 B，最后是 A。
2. 完成顺序. 各结点完成的顺序是 F、C、E、D、B、A。把它反过来，就得到第二趟的处理顺序：A、B、D、E、C、F。
3. 转置整张图. 每条边都反向：B 到 A、C 到 B、A 到 C、D 到 B、E 到 D、D 到 E、F 到 C。
4. 第二趟，从 A 开始. 在转置图中 A 抵达 C，C 抵达 B，而 B 只能抵达已访问的 A。这棵树覆盖 A、C、B，因此第一个分量是 {A, B, C}。关键在于搜索无法溢出到 D 或 F，因为在转置图中那些边是朝内指的，而不是朝外。
5. 第二趟继续. 顺序中下一个未访问的结点是 D。在转置图中 D 抵达已访问的 B，以及 E，而 E 抵达的 D 也已访问。于是分量为 {D, E}。最后 F 仍未访问：在转置图中它只能抵达已访问的 C，因此它是单元素分量 {F}。

得到的分量依次是 {A, B, C}、{D, E}、{F}。把它与同一张图上的 Tarjan 对照：后者输出的是 {F}、{D, E}、{A, B, C}。两者都正确，找到的也是同样的三个分量，但 Kosaraju 按缩点图的正向拓扑序输出，而 Tarjan 按逆序输出。如果你后续的代码在意这个顺序，这个差别就是二者取舍的理由。

复杂度及其来源

时间: O(V + E) · 空间: O(V + E)

两次深度优先搜索各需 O(V + E)，构造转置图还需要对所有边扫一遍，同样是 O(V + E)。三者相加仍为 O(V + E)。真正让 Kosaraju 输给 Tarjan 的是空间：它必须保存转置后的邻接结构，也就是边表的第二份完整副本，为 O(V + E)；而 Tarjan 只需在原图之上额外记录 O(V) 的信息。在拥有数千万条边的图上，这个差别就是决定性的，这也是尽管两者时间复杂度完全相同、生产环境中通常仍选 Tarjan 的原因。

何时使用科萨拉朱强连通分量算法，何时不宜

所有线性的强连通分量算法都是 O(V + E)。区别在于内存、遍历趟数，以及代码写对的难易程度。

常见陷阱

• 按完成顺序正着用而不是倒着用. 第二趟必须按完成时间递减的顺序处理结点。若按递增顺序进行，就会从一个汇分量起步，DFS 会跨越分量边界蔓延，把本应彼此独立的强连通分量合并起来。这是 Kosaraju 最具代表性的错误。
• 在发现时而不是完成时把结点加入顺序. 结点必须在其递归结束时入栈，而不是在第一次被抵达时。发现顺序不携带该算法所依赖的任何信息。
• 两趟之间忘记重置已访问集合. 两次搜索彼此独立。若把第一趟的已访问标记带进第二趟，就什么都不会被探索，所有分量都会是空的。
• 原地做转置. 第二趟需要反向后的图，而完成顺序来自原图。直接改动原有的邻接表而不另建一份转置，会把两者同时破坏。
• 以为它能用在无向图上. 强连通性是有向图的概念。在无向图中，每个连通分量本来就平凡地强连通，用一次 DFS 或并查集回答这个问题要便宜得多。

常见问题

Kosaraju 算法是怎样工作的？

它先在原图上执行一次深度优先搜索，记录各结点完成的先后顺序。随后把每条边反向，再执行第二次深度优先搜索，并按完成时间递减的顺序处理结点。第二趟中生长出的每一棵树，恰好就是一个强连通分量。

为什么把边反向就能奏效？

反向保持了强连通性，因为当所有边翻转后，两个结点之间的往返路径依然存在。改变的是分量之间的方向。从最后完成的结点起步会让你落在缩点图的一个源分量中，反向之后它的出边变成入边，于是搜索被困在该分量内而无法逃逸。

Kosaraju 和 Tarjan 有什么区别？

两者都是 O(V + E)。Kosaraju 用两趟 DFS 外加一份转置图副本，因此需要 O(V + E) 的额外空间；Tarjan 只用一趟以及 O(V) 的额外空间。Kosaraju 更好讲解也更好实现，Tarjan 在实践中更快更省。此外二者输出分量的顺序恰好相反：Kosaraju 是缩点图的正向拓扑序，Tarjan 是逆序。

Kosaraju 算法的时间复杂度是多少？

O(V + E) 时间，来自两次线性遍历再加一次构造转置图的线性扫描。空间为 O(V + E)，因为必须保存转置图，这也是它与 Tarjan 在实践中最主要的差别。

Kosaraju 能在无向图上找分量吗？

能跑，但没有意义。在无向图中每个连通分量本来就已经是强连通的，因此一次 DFS 或一个并查集结构就能一趟找出它们，根本不必构造转置图。