그래프 자료구조를 탐색하는 두 가지 알고리즘이 있다.
너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이다.
BFS란?
너비 우선 탐색은 시작점으로부터 인접한 꼭짓점들을 탐색하는 방법이다. 시작점으로부터 가까운 점들 먼저 탐색하기에 뻗어나가는 모습이 된다.
BFS를 사용하는 경우는, 두 점 사이의 최단경로를 찾을 때 사용된다. 시작점으로부터 가까운 점들을 우선으로, 너비를 이용하여 탐색하기에 한 개 이상의 경로가 존재하더라도, 경로가 존재하기만 한다면 최단경로를 찾을 수 있다.
대신 BFS는 재귀호출을 할 수 없기에 탐색할 꼭짓점들을 큐(Queue)에 담기 위한 더 큰 저장공간이 필요하다. 또한 꼭짓점의 수가 증가할수록 탐색해야 하는 꼭짓점의 수 또한 증가하기에, 꼭짓점이 많은 그래프에서 실행할 때는 많은 시간이 소요될 수 있다.
PSEUDOCODE
BFS는 큐(queue)를 이용해 구현할 수 있다.
아래 수도코드에서는 한 꼭짓점마다 색(color), 거리(d), 부모(π)의 세가지 정보를 가진다.
색은 WHITE, GRAY, BLACK의 세가지 색이 있는데 각각
WHITE = 아직 탐색되지 않은 꼭짓점
GRAY = 탐색중인 꼭짓점
BLACK = 탐색 완료된 꼭짓점
이다. 즉 WHITE는 큐에 한번도 들어가 보지 않은 꼭짓점, GRAY는 큐에 들어가 있는 꼭짓점, BLACK은 큐에 들어갔다 나온 꼭짓점이다.
거리는 시작점 s로부터 해당 꼭짓점까지의 거리를 나타낸다.
부모는 해당 꼭짓점을 탐색한 꼭짓점을 나타낸다.
위 코드를 하나씩 보면, 우선 입력 변수로 그래프 G와 시작 꼭짓점(vertex) s를 입력받는다.
1-4. s 를 제외한 그래프의 모든 꼭짓점의 색(color), 거리(d), 부모(π)를 초기화 한다.
5-7. s의 색을 회색, 거리를 0, 부모를 NIL로 지정한다.
8-9. 빈 큐를 생성하고 s를 큐에 삽입한다.
10-17. 큐에서 s를 꺼내고, s에 인접한 모든 하얀색의 꼭짓점에 대해 색을 회색으로 변경, 거리를 1 증가, 부모를 s로 만든다. 그리고 해당 작업이 완료된 꼭짓점들을 큐에 넣는다.
Time Complexity
회색(GRAY)은 큐에 꼭짓점이 두 번 이상 들어가는 것을 방지한다. 따라서 도달 가능한 모든 정점은 한 번씩 큐에 삽입된다. 이때 O(V)의 시간이 소요된다(모든 꼭짓점을 찾아 삽입했기에). 또한 꼭짓점이 큐에 존재할 때만 인접한 꼭짓점을 탐색하므로, directed graph에서는 최대 한 번, undirected graph에서는 최대 두 번 O(E)의 시간으로 탐색한다. 따라서 시간 복잡도 총합은 O(V+E)이다.
EXAMPLE
자세한 설명
(a)
1. 시작점: s
2. s 제외 나머지 꼭짓점 초기화
3. s의 색을 회색, 거리를 0, 부모는 NIL로 변경
4. 큐(Q)에 s 삽입
Q [s]
(b)
1. Q에서 s 제거
2. s와 인접한 w와 r를 탐색
3. w와 r의 색을 회색, 거리를 1, 부모를 s로 변경
4. Q에 w, r 삽입
5. s를 검은색으로 변경
Q [w, r]
(c)
1. Q에서 w 제거
2. w와 인접한 t와 x를 탐색
3. t와 x의 색을 회색, 거리를 2, 부모를 w로 변경
4. Q에 t, x 삽입
5. w를 검은색으로 변경
Q [r, t, x]
(d)
1. Q에서 r 제거
2. r와 인접한 v 탐색
3. v의 색을 회색, 거리를 2, 부모를 r로 변경
4. Q에 v 삽입
5. r를 검은색으로 변경
Q [t, x, v]
(e)
1. Q에서 t 제거
2. t와 인접한 u 탐색 (x는 회색이므로 탐색하지 않음)
3. u의 색을 회색, 거리를 3, 부모를 t로 변경
4. Q에 u를 삽입
5. t를 검은색으로 변경
Q [x, v, u]
(f)
1. Q에서 x제거
2. x와 인접한 y 탐색 (u는 회색이므로 탐색하지 않음)
3. y의 색을 회색, 거리를 3, 부모를 x로 변경
4. Q에 y를 삽입
5. x를 검은색으로 변경
Q [v, u, y]
(g)
1. Q에서 v제거
2. v와 인접한 꼭짓점 없음
3. v를 검은색으로 변경
Q [u, y]
(h)
1. Q에서 u제거
2. u와 인접한 하얀색 꼭짓점 없음
3. u를 검은색으로 변경
Q [y]
(i)
1. Q에서 y제거
2. y와 인접한 하얀색 꼭짓점 없음
3. y를 검은색으로 변경
Q []
Q가 비어서 BFS 종료
BFS 코드 (Python)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
graph = {
's': ['r', 'w'],
'r': ['s', 'v'],
'v': ['r'],
'w': ['s', 't', 'x'],
't': ['w', 'x', 'u'],
'x': ['w', 't', 'u', 'y'],
'u': ['t', 'x', 'y'],
'y': ['x', 'u'],
}
def bfs(graph, s):
visited = dict()
withOutParent = list()
parent = dict()
queue = list()
visited[s] = [0, "NIL"]
queue.extend(graph[s])
for i in range(0, len(graph[s])):
parent[ graph[s][i] ] = s
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited[vertex] = [visited[parent[vertex]][0] + 1, parent[vertex]] #[거리, 부모]
withOutParent = graph[vertex]
withOutParent.remove(parent[vertex])
for v in withOutParent:
if v in queue:
withOutParent.remove(v)
queue.extend(withOutParent)
for i in range(0, len(withOutParent)):
parent[withOutParent[i]] = vertex
return visited
print(bfs(graph,'s'))
#출력
{'x': [2, 'w'], 'v': [2, 'r'], 's': [0, 'NIL'], 't': [2, 'w'], 'u': [3, 't'], 'y': [3, 'x'], 'w': [1, 's'], 'r': [1, 's']}
|
cs |
그래프는 위 예시의 그래프를 이용했다. 결과는 { 꼭짓점: [거리, 부모] } 형식으로 출력된다.
'Computer Science > 알고리즘' 카테고리의 다른 글
| 백준 1697번 숨바꼭질 (너비 우선 탐색 BFS) (0) | 2021.06.15 |
|---|---|
| 백준 7576번 토마토 (너비 우선 탐색 BFS) (0) | 2021.06.15 |
| 백준 2606번 바이러스 (너비 우선 탐색 BFS) (0) | 2021.06.15 |
| 백준 2667번 단지번호붙이기 (너비 우선 탐색 BFS) (0) | 2021.06.12 |
| 백준 2178번 미로탐색 (너비 우선 탐색 BFS) (0) | 2021.06.11 |