15강. 깊이 우선 탐색

[ 목차 ]

1. 깊이 우선 탐색

2. 타임스탬프

3. 깊이 우선 탐색 숲

4. 간선의 분류

 

1. 깊이 우선 탐색

1) 시작점을 기준으로 인접해 있는 V를 차례대로 이동하는 방식

2) 점점 거리가 깊어졌다가 되돌아오는 방식으로 탐색이 진행

3) 거리를 기준으로 하는 넓이 우선 탐색과 달리 시간, 순서를 기준으로 함

4) 수행 시간

 

2. 타임스탬프

1) 각 정점은 타임탬프를 두 개씩 가지고 있음

2) v.d 발견 시간 : 이전의 정점으로부터 현재의 정점이 발견되기까지 얼마나 걸렸는가?

3) v.f 완료 시간 : 현재 정점이 더이상 인접한 정점이 없어 탐색할 필요가 없을 때

4) 초기화한 정점 : 흰색, 발견된 정점 : 회색, 완료된 정점 : 검은색

5) 이동 가능하지만 이미 종료된 정점이 있을 경우 점선으로 표시

 

3. 깊이 우선 탐색 숲

1) 직전 정점 그래프는 깊이 우선 탐색 숲이 됨

2) 같이 깊이 탐색이라면 상위 정점들이 하위 정점들을 모두 포함

3) 따로 떨어지는 경우는 별개

 

4. 간선의 분류

1) 트리 간선

2) 후향 간선 B

3) 가로 간선 C

4) 전향 간선 F

5) 무방향성 그래프의 깊이 우선 탐색에서 그래프의 각 간선은 트리 간선이거나 후향 간선