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로 인해 다시 방문하게 된다. 이를 확인할 수만 있으면 Cycle을 찾을 수 있다.

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) 의 논리와 같다.