Dev.Basic/알고리즘
[c++] BFS(Breadth First Search) 알고리즘
zeekke
2019. 9. 19. 02:43
BFS 알고리즘은 너비를 우선으로 탐색하는 알고리즘 입니다.
즉, 현재 정점에 연결된 가까운 노드부터 탐구합니다.
주로 queue를 이용해서 구현합니다.
c++로 bfs를 구현해보겠습니다.
위 그래프에서 1 노드와 가까운 노드부터 탐색하고 노드 번호를 출력합니다.
vector 타입의 graph는 각 노드 간의 연결 정보를 나타냅니다.
queue 타입의 q는 노드들이 가까운 순서대로 출력되기 위해 사용됩니다.
vector 타입의 visit은 노드 방문 여부를 나타냅니다.
아래 코드를 참고해주세요.
|
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
|
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph(7, vector<int> ());
queue<int> q;
vector<bool> visit(7, false);
void dfs(int start) {
visit[start] = true;
q.push(start);
while (!q.empty()) {
start = q.front();
q.pop();
printf("%d ", start);
for (int i = 0; i < graph[start].size(); i++) {
if (!visit[graph[start][i]]) {
visit[graph[start][i]] = true;
q.push(graph[start][i]);
}
}
}
}
int main(void){
graph[1].push_back(2);
graph[2].push_back(1);
graph[1].push_back(3);
graph[3].push_back(1);
graph[2].push_back(4);
graph[4].push_back(2);
graph[2].push_back(3);
graph[3].push_back(2);
graph[2].push_back(5);
graph[5].push_back(2);
graph[3].push_back(4);
graph[4].push_back(3);
graph[3].push_back(6);
graph[6].push_back(3);
dfs(1);
return 0;
}
|