DFS & BFS
DFS와 BFS는 그래프 탐색의 기초적인 알고리즘입니다. 이것을 기반으로 구현할 수 있는 알고리즘도 있으니 꼭 알고 있어야만 하는 알고리즘이기도 합니다.
그래프 탐색을 하기 전에 알아두면 좋은 몇가지 용어가 있는데, ( 아래 그림을 참조... )
정점 : 동그라미 안에 숫자가 있는 것을 정점이라고 한다.
간선 : 정점을 이어놓은 부분을 간선이라고 한다.
1. DFS ( 깊이 우선 탐색 )
DFS는 깊이를 우선으로 탐색하는 알고리즘입니다.
시작 노드와 연결된 것을 쭉 타고가서 더 이상 연결된 것이 존재하지 않을 때까지 탐색을 한 다음에 그 다음 연결된 노드에 이 과정을 반복하며 탐색하는 방법입니다. 다음 그림을 보면,
깊이 우선 탐색을 1부터 진행하여 나오는 결과는
1 -> 2 -> 7 -> 8 -> 9 -> 3 과 4 -> 5 -> 6 입니다.
2. BFS ( 넓이 우선 탐색 )
BFS는 근처에 있는 것을 먼저 탐색하는 알고리즘입니다.
시작노드의 주변에 있는 것을 먼저 탐색하고 그에 연결된 노드도 같은 방법으로 근처에 있는 것을 먼저 탐색합니다.
이것도 위의 그래프를 예시로 들어 표현하자면,
1 -> 2 -> 3 -> 7 -> 8 -> 9 와 4 -> 5 -> 6 입니다.
3. DFS와 BFS 구현!
...DFS구현
DFS 구현은 인접리스트를 이용하는 방법과 vector에 배열을 이용하는 방법이 있는데, vector에 배열로 구현해 보도록 하겠습니다. 우선 이미 간 정점은 다시 재방문할 필요가 없으므로 체크해 놓을 배열이 하나 필요합니다.
그런 다음에 재귀로 돌리면 되는데... 여기서 주의 해야 할 것은 마지막에 return처리를 해주지 않으면 Runtime error가 납니다. 이유는 잘 모르겠지만, 재귀가 끝나지 않아서 나타나는 것 같습니다.
...BFS구현
BFS 구현도 역시 vector에 배열을 사용해 구현해 보겠습니다.
BFS도 역시 이미 간 정점은 재방문할 필요가 없기 때문에 체크 배열을 하나 만들어 놓습니다.
그런 다음에 DFS와 이 부분이 조금 다른데... BFS 구현에는 queue라는 자료구조를 씁니다. 첫 정점을 queue에 넣어두고 체크해 줍니다. 그리고 queue가 완전히 비어있을 때까지 반복을 돌리는데, 시작 정점을 먼저 queue에서 빼 낸 다음에 시작 정점을 기준으로 주위에 있는 정점들을 방문하게 됩니다. 방문을 하지 않았을 경우에는? queue에 해당 정점을 넣어주면 됩니다.
그러면 queue에 맨 앞에 있는 정점을 기준으로 근처를 뒤지는 형태가 나옵니다.
https://en.wikipedia.org/wiki/Breadth-first_search#/media/File:Animated_BFS.gif
멍하니 이 애니메이션을 보다보면 이해가 됩니다.
구현한 코드는 다음과 같습니다.
|
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
/*
ID : literhyeon
LANG : C++
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int V[1010];
vector<int> G[1010];
void dfs(int p) {
cout << p << " ";
V[p] = 1;
for(int i=0; i<G[p].size(); i++) {
if(!V[G[p][i]]) dfs(G[p][i]);
}
return;
}
void bfs(int p) {
for(int i=1; i<=1010; i++) V[i] = 0;
queue<int> Q;
Q.push(p);
V[p] = 1;
while(!Q.empty()) {
int st = Q.front();
Q.pop();
cout << st << " ";
for(int i=0; i<G[st].size(); i++) {
int ed = G[st][i];
if(!V[ed]) {
Q.push(ed);
V[ed] = 1;
}
}
}
}
int main()
{
int n, m; cin >> n >> m;
while(m--) {
int x, y; cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1; i<=n; i++)
sort(G[i].begin(), G[i].end());
/*
for(int i=1; i<=n; i++) {
cout << i << " : ";
for(int j=0; j<G[i].size(); j++) {
cout << G[i][j] << " ";
}
cout << "\n";
}*/
dfs(1);
cout << "\n";
bfs(1);
cout << "\n";
return 0;
}
|
cs |
여기서는 1번 정점부터 완전탐색을 진행하였는데, 조금 바꾸면 원하는 정점에서 시작할 수도 있습니다.