스택 기반 DFS를 사용하는 방향성 그래프의 사이클 감지

Question

스택 오버플로 예외 발생 후 algo가 실패합니다. Directed Graph에서주기 탐지를 위해이를 어떻게 수정할 수 있는지 또는 가능한 경우 재귀 대신 스택을 기반으로 누군가를 제공 할 수 있는지 알려 주시기 바랍니다.

public boolean hasCycle(Graphnode<T> n) { 

    n.setMark(IN_PROGRESS); 

    for (Graphnode<T> m : n.getSuccessors()) { 
     if (m.getMark() == IN_PROGRESS) { 
      return true; 
     } 

     if (m.getMark() != DONE) { 
      if (hasCycle(m)) { 
       return true; 
       } 
     } 
    } 

    n.setMark(DONE); 

    return false; 
} 

감사합니다, Vikrant

Answer 1

나는 오랫동안 이런 종류의 물건을하지 않은하지만 코드가 이상한 것 같다. 첫 번째 경우 조건은 다음과 같습니다

if (m.getMark() == IN_PROGRESS) { 

return true; 
} 

나는 대신이해야한다고 생각 :

if (m.getMark() == IN_DONE) { 

return true; 
} 

하지 않으면 m.getMark() == IN_PROGRESS 및 m.getMark() != DONE의 차이점은 무엇입니까? 두 번째 if-condition이 실행되지 않습니다.

참고 : DFS 또는 스택을 사용하는 많은 알고리즘을 찾을 수 있습니다.