지난 글 : [알고리즘] - 그래프
너비 우선 탐색은 그래프를 탐색하는 알고리즘이다. 최초 시점에 자신이 특정 정점(시작점)에 있다고 하자. 단, 그래프의 전체 구조는 모른다. 목적은 시작점에서 간선을 따라 가며 정점을 탐색하고 지정한 정점(목표)에 도달하는 것이다. 정점에 도착하면 해당 점이 목표인지를 판단할 수 있다. 너비 우선 탐색이란, 정점을 탐색할 때 시작점에 가까운 정점부터 탐색하는 방식이다.
1
"A"
/ | \
B C D
/ | | | \
E F H I J
/ | \
K G L자신이 현재 있는 정점을 " "로 표시한다(책에서는 빨간색).
A를 시작점, G를 목표라 한다. 처음에는 시작점 A에 있으며 G가 어디에 있는지 모른다.
2
"A"
/ | \
'B C D'
/ | | | \
E F H I J
/ | \
K G L후보 정점들을 ' ' 로 표시한다(책에서는 초록색).
A에서 도달할 수 있는 정점 B, C, D가 다음 이동 대상 후보가 된다.
3
"A"
/ | \
'B C D'
/ | | | \
E F H I J
/ | \
K G L후보들 중 하나의 정점을 선택한다. 선택 기준은 가장 먼저 후보에 추가된 것으로 한다. 같은 시점에 후보가 된 정점의 경우 아무거나 선택해도 된다. 여기서는 왼쪽에 있는 정점부터 선택한다. 이 경우 B, C, D는 같은 시점에 후보가 됐으니 가장 왼쪽에 있는 B를 선택한다. (책에서 선택된 정점은 주황색으로 표시)
4
A
/ | \
"B"'C D'
/ | | | \
E F H I J
/ | \
K G L(책에서 A는 탐색이 끝났으므로 주황색으로 바뀜) 선택한 정점 B로 이동한다.
A
/ | \
"B"'C D'
/ | | | \
'E F' H I J
/ | \
K G L현재 B에서 도달할 수 있는 E와 F가 새로운 후보로 추가된다. 후보 중 가장 먼저 추가된 것은 C와 D다. 이 중 가장 왼쪽 C를 선택한다.
A
/ | \
B "C"'D'
/ | | | \
'E F' H I J
/ | \
K G L선택한 정점(C)으로 이동한다.
5
A
/ | \
B "C"'D'
/ | | | \
'E F''H' I J
/ | \
K G L현재 위치인 C에서 도달할 수 있는 H를 새로운 후보로 추가한다. 같은 작업을 목표에 도달하거나 모든 정점의 탐색이 끝날 때까지 반복한다.
A
/ | \
B C D
/ | | | \
"E"'F''H''I J'
/ | \
'K' G L여기서는 A, B, C, D, E, F, H, I, J, K순으로 선택된다.
6
A
/ | \
B C D
/ | | | \
E F H I "J"
/ | \
'K' 'G' 'L'A부터 I까지 탐색한 후 현재 J에 있다.
7
A
/ | \
B C D
/ | | | \
E F H I J
/ | \
K "G" L목표 G에 도달했으므로 탐색을 종료한다.
너비 우선 탐색은 이처럼 시작점부터 가까운 순으로 너비를 넓혀 가며 탐색하는 방식이다. 따라서 목표가 시작점 가까이 있으면 탐색이 빨리 종료된다.
참고 서적 :
