시간 순서기반으로 탐색

깊이 우선 탐색

타임 스탬프 (Timestamps)

• 각 정점은 타임스탬프를 두 개씩 가지고 있다.
  • $v.d$: 발견 시간
  • $v.f$: 완료 시간

정점의 색 구분 (Colors of vertices)

• 초기화한 정점 : 흰색 - not discovered
• 발견된 정점 : 회색 - discovered
• 완료된 정점 : 검은색 -finished

---

사용하는 자료구조 : 스택

깊이 우선 탐색 숲

• 직전 정점 그래프는 깊이 우선 탐색 숲이 된다.
  • forest : 그래프, 무방향성, 사이클이 없어야함

Parenthesis theorem ( for gray interval)

• 같이 깊이 탐색이라면 상위 정점들이 하위 정점들을 모두 포함
• 따로 떨어진 경우는 별개

간선의 분류

• 트리 간선
• 후향 간선
• 가로 간선
• 전향 간선