强连通分量: Kosaraju算法

Question

在Kosaraju算法中，我遇到了两个可能的实现：

1)根据原图中顶点的拓扑顺序，搜索逆图中的强连通分量。

( 2)在原图中按反图顶点的拓扑顺序搜索强连通分量。

我想这样做是错误的，它是错误的，在原来的图中搜索强连通的分量时，使用的是反向拓扑顺序的顶点。这在内存方面也会更好，因为不需要一个新的邻接列表。

资料来源:1) E-Maxx，2) CLRS图书。

Answer 1

术语问题：

你说的是拓扑序，但拓扑序存在的当且仅当图是DAG (有向无圈)。如果您只想使用DAGs，那么您已经有SCC (强连接组件)，因为每个顶点本身都是组件。如果要在有向图上找到SCC，则需要将拓扑排序更改为DFS完成时间。CLRS书只提到完成时间f[u]

1. 调用DFS(G^T)，但在DFS的主循环中，考虑顶点的递减顺序。

改写你的问题：

在原图中搜索强连通分量是错误的，考虑顶点的顺序是增加收尾次数f[u]？

答案：

是的，这是错误的。

反例:考虑下面的图表：

​

​

它包含两个组件C和C'。如果您运行第一个DFS (从节点u开始)，那么在结束时间后，您将得到以下两个列表中的一个，按升序排列：

外勤部名单1：{v,w',w,u}

外勤部名单2：{w',v,w,u}

您实际上要问的是，您是否能够从原始图的一开始就处理这些列表。如果选择第一个列表，将从节点v开始通过DFS搜索提取组件C，然后从节点w'开始通过DFS搜索提取组件C。但是，如果选择第二个列表并从原始图上的节点w'启动DFS，则只会得到一个组件(整个图)，这是错误的。

注意，Kosaraju的算法在这两种情况下都有效，因为它从列表的末尾开始(两种情况下都是节点u )，并通过对反向图的DFS搜索提取组件C。当我们到达列表中的节点C'时，组件v将被提取。

Answer 2

Kosaraju算法是一种线性时间算法，用于寻找一个强连通分量，它既可以用于有向图，也可以用于无向图。为了更简单，我们可以在图中说，如果任何一组节点都是一个强连接组件(SCC)。如果我们讨论Brute力方法来解决这个问题，我们可以按照以下步骤：

1. 使用Floyd算法找到所有对最短路径。
2. 检查任意两对之间的距离是否为无穷远，即不可达，那么它不是SCC，否则是SCC。

如果我们讨论这种方法的复杂性，则需要三次时间，即O(v^3)。因此，我们可以使用Kosaraju算法优化这种方法，该算法可以在O(n+m)时间内运行我们的算法。使用Kosaraju算法解决强连通组件问题的步骤如下：

1. 对图执行深度优先搜索(DFS)，并将节点推送到堆栈。
2. 通过倒置图的边，找到图的转置。
3. 从堆栈中逐个弹出节点，并在修改后的图上再次执行DFS。

每个成功的1-SCC强连接component.This是Kosaraju算法在O(n+m)时间中的工作方式，其中n是图中的节点数，mE 249是边数。