2

我需要找到有向图的强连通分量。我决定使用 Tarjan 的算法。到目前为止，一切都很好。但是，我需要我的程序操作的数据集是巨大的，并且我得到了 stackoverflow 异常。我无法增加堆栈大小，所以我需要找到另一个解决方案。

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

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

感谢您的任何建议！

4

2 回答 2

1

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

  • 与递归共存。不是一个真正的选择，每个节点的递归将很快填满堆栈
  • 用迭代重写递归，为 DFS 提供你自己的堆栈。不难，推荐这个
  • 发明一种非递归算法。在这种情况下祝你好运
于 2012-04-10T12:10:41.150 回答
0

我也遇到了这个问题，我发现两个解决这个问题的最好方法是将所有代码转移到一个新线程，如下所示：

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)

第一个参数为null，第二个参数是你想在这个线程上运行的类，第三个参数只是一个名字，它不是很重要，最后一个参数是你想分配给这个线程的堆栈大小，我认为在这个示例堆栈大小为 2^32 字节（我不确定！）

在这里您可以找到更多关于ThreadJava 的信息：https ://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html

这些例子是用 Java 编写的；您可以在任何其他面向对象的语言中做同样的事情。

于 2017-01-03T16:40:01.780 回答