지난 글 : [알고리즘] - 너비 우선 탐색
깊은 우선 탐색은 너비 우선 탐색과 마찬가지로 그래프를 탐색하는 알고리즘이다. 시작점으로부터 지정한 정점(목표)에 도달하는 것이 목적이다. 깊이 우선 탐색에서는 정점을 탐색할 때 하나의 길을 끝까지 따라가며 더 이상 진행할 수 없는 곳에 다다르면 다음 후보가 되는 길을 따라간다.
1
"A"
/ | \
B C D
/ | | | \
E F H I J
| | |
K G LA를 시작점, G를 목표로 한다. 현재 위치는 " "로 표시한다.
2
"A"
/ | \
'B C D'
/ | | | \
E F H I J
| | |
K G LA에서 도달할 수 있는 정점 B, C, D를 다음 후보로 표시한다. 후보는 ' '로 표시한다.
3
A
/ | \
"B"'C D'
/ | | | \
'E F' H I J
| | |
K G L후보 중 하나의 정점을 선택할 때 기준은 후보 중 가장 최근(가장 늦게) 추가된 것이다. 같은 시점에 후버가 된 정점은 어느 것을 선택해도 상관없다. 여기서는 왼쪽에 있는 정점을 선택한다. B로 이동한다. B로부터 도달할 수 있는 E와 F를 새로운 후보로 추가한다.
4
A
/ | \
B 'C D'
/ | | | \
"E"'F' H I J
| | |
'K' G L가장 최근 후보에 추가된 E와 F 중 왼쪽에 있는 E로 이동한다. 현재 위치에서 도달할 수 있는 K를 새로운 후보로 추가한다.
5
A
/ | \
B 'C D'
/ | | | \
E "F" H I J
| | |
K G L같은 작업을 목표에 도달하거나 모든 정점의 탐색이 끝날 때까지 반복한다.
6
A
/ | \
B "C"'D'
/ | | | \
E F 'H' I J
| | |
K G L현재 C까지 탐색했다.
7
A
/ | \
B C 'D'
/ | | | \
E F H I J
| | |
K "G" LG에 도착했으므로 탐색을 종료한다.
깊이 우선 탐색은 너비 우선 탐색과 탐색 순서는 다르지만 처리상 차이점은 후보 정점 중 다음에 이동할 정점을 선택하는 기준 하나만 다를 뿐이다. 너비 우선 탐색은 가장 먼저 후보가 된 것을, 깊이 우선 탐색은 가장 최근에(늦게) 후보가 된 것을 선택하므로 각각 시작점에 가까운 정점부터 탐색, 새로운 길을 찾아 탐색하는 것이다.
참고 서적 :
'알고리즘 > 알고리즘 도감' 카테고리의 다른 글
| 다익스트라 알고리즘 (0) | 2022.06.20 |
|---|---|
| 벨먼-포드 알고리즘 (0) | 2022.06.19 |
| 너비 우선 탐색 (0) | 2022.06.16 |
| 그래프 (0) | 2022.06.15 |
| 이진 탐색 (0) | 2022.06.14 |
