找到强连通的组件 - 无递归

Question

我需要找到有向图的强连通组件。 我决定使用Tarjan的算法。到现在为止还挺好。 然而，我需要我的程序来操作的数据集是巨大的，我得到了stackoverflow异常。我不能增加堆栈大小，所以我需要找到另一个解决方案。

我可以改变递归算法迭代，但我想知道是否有“更清洁的解决方案”。

我想不是，但我想确保在我开始实施迭代版本之前。

感谢您的任何建议！

Answer 1

寻找SCC已知算法都是基于DFS，这在本质上是递归的，所以你基本上有以下选项：

• 住递归。不是真正的选择，每个节点的递归将快速填充堆栈
• 用迭代重写递归，为DFS提供自己的堆栈。没那么难，我推荐这个
• 发明了一种非递归算法。在这种情况下

Answer 2

我也有这个问题，我找到了最好的路两解决这个问题是所有的代码转移到一个新的线程像这样的好运气：

public class Class implements Runnable { 
    @Override 
    public void run() { 
     ... 
    } 
} 

，并在您主类你这样做：

public class Main { 
    public static void main(String[] args) { 
     Thread th = new Thread(null, new Class(), "solution", 32 << 20); 
     th.start(); 
    } 
} 

Thread(ThreadGroup group, Runnable target, String name, long stackSize) 

第一个参数为空，第二个参数是要在这个线程运行的类，第三个参数只是一个名字的不是很重要，而最后一个参数是堆栈你想要的大小分配给该线程，我认为，在这个例子中堆栈大小为2^32字节（我不知道！）

在这里你可以找到更多关于Thread在Java中：https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html

这些例子是Java ;你可以在任何其他面向对象的语言中做同样的事情。