알고리즘 7장

그래프 판정: 방향 그래프 사이클 검사(DFS 상태)

방향 그래프 사이클 검사는 unvisited, visiting, done 세 상태로 DFS 진행 중 되돌아가는 간선을 찾습니다.

상태 변화

3색 상태
Avisiting
Bvisiting
Cvisiting
Ddone
A→B→C↩A

현재 경로 위의 visiting 정점으로 돌아가면 방향 그래프 사이클입니다.

불변식

점검
unvisited아직 DFS에 들어가지 않은 정점입니다.
visiting현재 재귀 경로 위에 있어 다시 만나면 사이클입니다.
done하위 탐색이 끝나 더 이상 경로 위에 없는 정점입니다.
주의무방향 그래프의 parent 체크 방식과 섞으면 오답이 납니다.