강력하게 연결된 구성 요소 찾기 - 재귀 호출하지 않음

Question

유향 그래프의 강하게 연결된 구성 요소를 찾아야합니다. 나는 Tarjan 알고리즘을 사용하기로 결정했습니다. 여태까지는 그런대로 잘됐다. 그러나 데이터 세트에서 작동하려면 프로그램이 필요하고 거대한 스택 오버 플로우 예외가 발생합니다. 스택 크기를 늘릴 수 없어 다른 솔루션을 찾아야합니다.

재귀 알고리즘을 반복적으로 변경할 수는 있지만 "깨끗한 해결책"이 있는지 궁금합니다.

반복 버전을 구현하기 전에 확신하고 싶습니다.

의견을 보내 주셔서 감사합니다. SCC를 찾는

Answer 1

알려진 알고리즘은 모든 자연의 재귀 DFS에 기반하고, 그래서 당신은 기본적으로 이러한 옵션을 가지고 :

• 은 재귀와 함께 살고 있습니다. 옵션이 아니라 모든 노드에 대한 재귀가 스택을 빠르게 채울 것입니다.
• 반복을 사용하여 재귀를 다시 작성하고, DFS에 대한 스택을 제공하십시오. 그다지 열심히, 나는 이것을 추천 할 것이다
• 비 재귀 알고리즘을 발명한다. 이 경우

Answer 2

나도이 문제를 가지고 내가이이 문제는 다음과 같이 새로운 Thread에 모든 코드를 전송하는 것입니다 해결하는 가장 좋은 방법을 발견의 행운을 빕니다 :

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의 경우, 두 번째 매개 변수는이 스레드에서 실행하려는 클래스이며, 세 번째 매개 변수는 이름이 매우 중요하지 않다, 마지막 매개 변수는 스택이다 원하는 크기 https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html

이러한 예는 자바에있는이 스레드에 할당 내가이 예 스택의 크기를 생각하면 2^32 바이트 (! 잘 모르겠어요)

다음

자바에 더 약 Thread 알 수있다 ; 당신은 다른 어떤 객체 지향 언어에서도 똑같이 할 수 있습니다.