Directed 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를 방문하고 있는지 확인하기 위해, stack용 visited를 추가하면 된다.
즉, 중복 방문 방지를 위해선 visited를 사용하고, cycle 탐지를 위해선 stackVisited 를 사용하여 DFS하면 된다.

solution 2)

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

1. White: 처리되지 않음.
2. Gray: 처리중.(rec stack에 존재)
3. Black: 처리 완료. 즉, 모든 인접 nodes까지 방문 완료.

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

vs Undirected Graph Cycle

directed graph와 undirected graph에서 cycle 탐지는 어떤 차이가 있을까?

undirected에서는, dfs call이 오면 해당 node를 visited 처리한다.
이후 dfs 과정에서 adjNodes중 parent가 아닌데도 visited 라면 cycle이다.

반면, directed에서는 이런 식으로 처리할 때, visited 상태더라도 방향에 따르면 cycle은 아닐 수도 있다. 이를 구분해내기 위해, stack용 visited 또는 color로 구분하는 것이다.