무한 루프에서 스택 오버플로 - 수정 된 DFS의 사이클을 감지

Question

이 시점에서 무한 루프의 소스를 확인하려고 조금 미쳤습니다 (stackoverflow 오류 발생). 그래프에서 사이클을 감지하기 위해 수정 된 DFS를 구현하려고합니다. 이 예제에서는 11 페이지에서 작업하고 있습니다. http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf

이 구현에서는 0 = 흰색, 1 = 회색 및 2 = 검정입니다. 나는 비교적 간단한 것을 놓치기를 바라고 있습니다.

public boolean containsCycle() 
{ 
    for (int i=0; i<n; i++) 
    marks[i] = 0; // Initialize all to zero - unvisited 

    for (int i=0; i<n; i++) { // n = number of vertices in the graph 
    if (marks[i]==0) { 
     if (visit(i)){ 
     return true; 
     } 
    } 
    } 
    return false; 
} 

public boolean visit(int index){ 
    marks[index] = 1; // Visited 

    for (int i=0; i<n; i++){ 
     if(isArc(index,i)){ // isArc() returns true IFF there is a directed edge from index-> 
     if (marks[i]==1) 
     return true; 
     } 
     else if (marks[i]==0) { 
     if(visit(marks[i])) 
     return true; 
     } 
    } 
    marks[index] = 2; 
    return false; 
    } 

Answer 1

는 대신