找到強連通的組件 - 無遞歸

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 ;你可以在任何其他面向對象的語言中做同樣的事情。