Graph를 Depth First Search 하면 하나의 Tree를 만들 수 있다. 이때, 이 Tree에 back edge가 존재하면, Cycle이 있다고 말한다

Tree에서 Back Edge는, 현재 node에서 자기 조상의 node로 가는 edge를 말한다.(자기 자신으로 가는 것도 포함)

어떻게 하면 Cycle을 찾을 수 있을까?

Solutions

DFS는 Stack을 이용한다. 이때, Cycle이 있는 Graph를 순회하면, 현재 Stack에 올라와 있는 node를, back edge로 인해 다시 방문하게 된다. 이것을 확인하면 되는데, 방법은 다양하다.

solution 1)

Stack에 올라와 있는 node를 방문하고 있는지 확인하기 위해, 해당 nodes가 Stack에 올라와 있는지, 체크용 bool array를 추가하면 된다.

solution 2)

두 번째 방법은, 일반적인 DFS에서 사용하는 visited를 변형하는 것이다. 기존의 visited는 두 가지 color를, 방문한 nodes와 방문하지 않은 nodes를 구별하기 위해 사용했다. 이것을 변형하여, visited에서 세 가지 color를 사용하는 방법이 있다.

1. White: 처리되지 않음.
2. Gray: 처리중.
3. Black: 처리 완료. 즉, 모든 인접 nodes 방문 완료.

현재 상태가 Gray인 node는 stack에 올라와 있는 상태이다. 즉, Gray인 node에 접근하게 되면 Cycle이 존재하는 것으로, solution 1) 의 논리와 같다.