有一种著名的算法可以找到称为 的强连通分量Kosaraju's algorithm，它使用两个 DFS 来解决这个问题，并θ(|V| + |E|)及时运行。

首先，我们在图的补集 ( G^R ) 上使用 DFS 来计算顶点的反向后序，然后我们在主图上应用第二个 DFS，方法是G采用反向后序的顶点来计算强连通分量。

尽管我了解算法的机制，但我并没有得到反向发布顺序需要背后的直觉。

它如何帮助第二个 DFS 找到强连接组件？

• 我为已超过截止日期的作业编写了此代码。

• 此实现完全适用于各种较小的测试用例，并在图中显示了 5 个最大的强连接组件的大小。

• 但是当我在大约 875714 个顶点的分配数据集上运行它时，它似乎永远执行。（60 分钟后甚至没有从第一次 DFS 通行证中出来）

• 我使用了 DFS 例程的非递归堆栈实现，因为我听说大量顶点导致递归堆栈溢出问题。

• 如果有人能指出，这将非常有帮助，这段代码中的什么使它在大型数据集上表现得这样。

• 输入文件由图中的边列表组成。一条边/线。

（例如）：

1 2

2 3

3 1

3 4

5 4

大图测试用例 zip 文件的下载链接

链接到我的程序文件

代码如下：

//宏定义和全局变量

//非递归DFS算法

// 2 pass Kosaraju 算法

.

作为作业的一部分，我正在尝试在大图上实现 Kosaraju 的算法 [MOOC Algo I Stanford on Coursera]

https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

当前代码在一个小图上工作，但我在运行时执行期间遇到了 Stack Overflow。

尽管已阅读 F# 专家中的相关章节，或网站和 SO 上的其他可用示例，但我仍然不知道如何使用 continuation 来解决这个问题

下面是通用的完整代码，但是在执行 DFSLoop1 和里面的递归函数 DFSsub 时它已经失败了。我认为我没有使函数尾递归[因为说明

?]

但我不明白如何正确实施延续。

当只考虑失败的部分时，DFSLoop1 将我们将应用深度优先搜索的图作为参数。我们需要将完成时间记录为算法的一部分，以便在第二个 DFS 循环 (DFSLoop2) 中继续进行算法的第二部分 [当然在此之前我们失败了]。

这是一个带有简单图形示例的文本文件

（导致溢出的一个是 70Mo 大，大约有 900,000 个节点）

编辑

首先澄清一些事情这是“伪代码”

输入：以邻接表表示的有向图 G = (V,E)。假设顶点 V 标记为 1、2、3、...。. . , n. 1. 让 Grev 表示所有弧的方向都被反转后的图 G。2. 在Grev 上运行DFS-Loop 子程序，按照给定的顺序处理顶点，得到每个顶点v ∈ V 的完成时间f(v)。3. 在 G 上运行 DFS-Loop 子程序，按照 f(v) 的降序处理顶点，为每个顶点 v ∈ V 分配一个领导者。4. G 的强连通分量对应于 G 的顶点，它们共享一个共同的领导者。 图 2：我们的 SCC 算法的顶层。f 值和领导者分别在对 DFS-Loop 的第一次和第二次调用中计算（见下文）。

输入：以邻接表表示的有向图 G = (V,E)。1. 将全局变量 t 初始化为 0。[这会跟踪已完全探索的顶点数。] 2. 将全局变量 s 初始化为 NULL。[这会跟踪调用最后一次 DFS 调用的顶点。] 3. 对于 i = n 到 1： [在第一次调用中，顶点标记为 1、2、...。. . , n 任意。在第二次调用中，顶点由第一次调用的 f(v) 值标记。] (a) 如果 i 尚未探索：i。设置 s := i ii。DFS(G, i) 图 3：DFS-Loop 子程序。

输入：有向图 G = (V,E)，采用邻接表表示，源顶点 i ∈ V。1. 将 i 标记为已探索。[在整个 DFS-Loop 调用期间一直在探索。] 2. 设置 leader(i) := s 3. 对于每个弧 (i, j) ∈ G：(a) 如果 j 尚未探索：i。DFS(G, j) 4. t + + 5. 设置 f(i) := t 图 4：DFS 子程序。f 值只需要在第一次调用 DFS-Loop 时计算，而领导值只需要在第二次调用 DFS-Loop 时计算。

编辑 我已经修改了代码，在经验丰富的程序员（一个 lisper 但没有 F# 经验）的帮助下，稍微简化了第一部分，以便更快地获得一个示例，而无需担心与此讨论无关的代码。

代码只关注算法的一半，运行一次 DFS 以获得反向树的完成时间。

这是代码的第一部分，只是为了创建一个小示例 y 是原始树。元组的第一个元素是父元素，第二个元素是子元素。但我们将使用反向树

所以基本上图表是 (1->2->3->1)::(4->5->6->7->8->....->99999->10000) 和反向图是 (1->3->2->1)::(10000->9999->....->4)

这是以直接样式编写的主要代码

它不是尾递归的，所以我们使用延续，这里是适应 CPS 风格的相同代码：

两个代码都编译并为小示例（注释中的那个）或我们正在使用的同一棵树提供相同的结果，但大小更小（1000而不是100000）

所以我不认为这是算法中的错误，我们有相同的树结构，只是更大的树导致了问题。在我们看来，续篇写得很好。我们已经明确输入了代码。并且所有呼叫在所有情况下都以继续结束...

我们正在寻求专家建议！！！谢谢 ！！！

这是我编写的使用 Kosaraju 的两次通过算法查找 SCC 的代码。当我运行 main 方法时，我在 SCC.revDFS 上得到一个 StackOverFlowError。有大量递归调用时如何避免堆栈溢出错误？

我目前有一个 Kosaraji 算法的工作实现，给定一个没有权重的有向图，将在图中打印 SCC。

我想对其进行调整，以便它还会说明 SCC 之间的边缘在哪里。

这是代码：

对于给定的图表：

{1,2,3} -> {8,7,9} {1,2,3} -> {4,5,6}

意思是，{1,2,3} 和 {8,7,9} 之间有一条边。之间还有一条边：{1,2,3} -> {4,5,6}

但是，{8,7,9} 和 {4,5,6} 之间没有边

目标是跟踪这些，以确定从任何给定顶点开始可能接触的最大 SCC 数量。我如何修改此代码以将其生成为图形？

I'm currently trying to implement the Kosaraju's algorithm on directed graph to find all strongly connected components.

I understand quite well how this algorithm works, but I have some issues when getting the post-visit order of the DFS result.

For now, the pseudo code of my DFS implementation is the following :

[EDIT] : I finally got a DFS version with the post visit order as output. I thought about increment a number representing the "lock" of a node each time this node push a neighbour on the DFS stack. Then when a node's visit is ended (no more neighbours to push), I notice the one which pushed it that the DFS from this child is ended (I decrement its lock). If this notification ends the visit of the preceding too, I go up to the previous preceding node to notice it, etc...

But I'm not sure that this kind of implementation outputs the right post order for Kosaraju's algorithm.

Is my DFS right or not ?

Example of my DFS :

(I listed the vertices clockwise, so a = 0, b = 1, c = 2, d = 3, h = 4, g = 5, f = 6, e = 7)

EDIT: I put some extra informations about how I get the results and how I run the algorithm by hand. Hope it is clearer now.

谁能解释一下 Kosaraju 寻找连通分量的算法背后的逻辑？

我已经阅读了描述，但我无法理解反向图上的 DFS 如何检测强连接组件的数量。

在上面你可以找到我的实现。我猜初始 DFS 和反向操作都正确完成了，但我不知道如何正确执行第二个 DFS。提前致谢。

我有一个 Kosaraju 算法的实现，用于在 Python 中查找 SCC。下面的代码包含一个递归（在小型测试用例上很好）版本和一个非递归版本（由于真实数据集的大小，我最终需要它）。

我已经在一些测试数据集上运行了递归和非递归版本并得到了正确的答案。然而，在我最终需要使用的更大的数据集上运行它会产生错误的结果。浏览真实数据并不是一个真正的选择，因为它包含近一百万个节点。

我的问题是我不知道如何从这里开始。我的怀疑是我要么在我的测试用例中忘记了某个图形星座的案例，要么我对这个算法应该如何工作有一个更根本的误解。

跑步：

最复杂的测试用例（SCC_5.txt）：

该测试用例的绘图：https ://imgur.com/a/LA3ObpN

这会产生 4 个 SCC：

• 底部：尺寸 4，节点 2、8、6、11
• 左：尺寸 3，节点 1、10、4
• 顶部：尺寸 1，节点 5
• 右：尺寸 3，节点 7、3、9

我在 Python 3 中编写了 Kosaraju 的两遍算法，当前的实现找到 SCC 并根据每个 SCC 中的节点数确定每个 SCC 的大小。然后，确定最大的 SCC。如何更改代码，以便它可以根据每个 SCC 中的边数计算每个 SCC 的大小。

例如对于一个图（下面以列表的形式呈现，只是为了简单起见）：[[1,2],[2,3],[2,5],[3,4],[4 ,1],[5,6],[6,7],[7,5]] 第一个元素是尾部，第二个元素是头部。

上述代码的结果，包括按降序排列的 SCC 的大小，是 [4,3]

但是，当前的实现导致图的数字相同：[[1,2],[1,3],[2,3],[2,5],[3,4],[4,1 ],[5,6],[6,7],[7,5]] 有一个附加边 [1,3]。我想要 [5, 3] 作为结果。任何帮助深表感谢。

2-SAT 问题，寻找变量的值

我正在使用这个解决方案来寻找给定公式的可满足性。（通过检查 SCC）。如果公式可满足，是否有任何有效的方法（在我的情况下，有效意味着不比多项式时间差）如何找到每个变量的值？

它不必在 C++ 中，我只是使用相同的算法。