[Graph] BFS 너비 우선 탐색
Graph Algorithm
01. 너비 우선 탐색 (Breadth First Search)
- 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘
- 시작점과 가까운 것 위주로 탐색하는 기법
- 맹목적인 탐색 하고자 할 때 사용하는 방법
- Quere를 사용해 알고리즘이 수행된다.
(아래 ‘=’ 사이에 노드가 들어가는 큐를 의미한다.)
- BFS는 시작 노드(Start Node)를 큐에 삽입하며 시작한다.
- 삽입한 노드들은 ‘방문 처리’ 해준다. (분홍색으로 표시)
BFS는 다음과 같은 알고리즘에 따라 작동한다.
- 큐에서 하나의 노드를 꺼낸다
- 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.
- 위 과정을 반복수행한다.
- 큐에서 꺼낸 Start 노드 1과 인접한 노드인 2와 3을 방문한 뒤 큐에 삽입한다.
- 큐에서 꺼낸 노드인 2와 인접한 노드 4, 5를 방문하고 큐에 삽입한다.
- 큐에서 꺼낸 노드인 3과 인접한 노드 6, 7을 방문하고 큐에 삽입한다.
- 큐에서 다음 노드를 꺼내고, 더이상 방문할 노드가 존재하지 않으므로 차례로 큐에서 노드를 꺼낸다.
Source Code
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int number = 7;
int c[7];
vector<int> a[8];
void bfs(int start) {
queue<int> q;
q.push(start);
c[start] = true;
while(!q.empty()) {
int x = q.front();
q.pop();
printf("%d ", x);
for(int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if(!c[y]) {
q.push(y);
c[y] = true;
}
}
}
}
int main(void) {
// 1과 2을 연결합니다.
a[1].push_back(2);
a[2].push_back(1);
// 1과 3를 연결합니다.
a[1].push_back(3);
a[3].push_back(1);
// 2과 3를 연결합니다.
a[2].push_back(3);
a[3].push_back(2);
// 2과 4을 연결합니다.
a[2].push_back(4);
a[4].push_back(2);
// 2과 5를 연결합니다.
a[2].push_back(5);
a[5].push_back(2);
// 3와 6를 연결합니다.
a[3].push_back(6);
a[6].push_back(3);
// 3와 7을 연결합니다.
a[3].push_back(7);
a[7].push_back(3);
// 4와 5를 연결합니다.
a[4].push_back(5);
a[5].push_back(4);
// 6과 7을 연결합니다.
a[6].push_back(7);
a[7].push_back(6);
// BFS를 수행합니다.
bfs(1);
return 0;
}
BFS
- 너비우선 탐색의 방법이 다른 알고리즘에 적용이 되어 효과적으로 사용이 된다는 것 자체에 의미가 있다.
- BFS는 하나의 탐색 방법이기 때문에 이 자체는 큰 의미가 없다.
- 나중에 응용을 위해 개념을 배운 것!
