너비 우선 탐색(BFS, Breadth-first search)
1. BFS란?
- 트리나 그래프를 순회하는 방법중의 하나이다. BFS와 대응되는 다른 탐색 방식으로는 DFS가 있다.
- 두 노드 사이의 최단거리를 구할 수 있다.
- 그래프 순회에서 분기(branch)가 발생할 경우 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다. 다음 그림과 같은 탐색 순서를 따른다.
이미지: Wikipedia Blake Matheny / CC BY-SA
2. BFS의 구현
BFS는 주로 큐를 사용하여 구현한다.
큐를 사용한 구현 (C++)
그래프를 탐색하는 함수만 구현하였다.
큐 또는 C++의 <queue>이 궁금하다면 여기
#include <cstdio>
#include <queue>
using namespace std; // STL 선언
int visit[99]; // 방문 여부 기록용
int node[99][99]; // 그래프를 인접 행렬로 기록했다고 가정, 0번은 NULL.
queue<int> q; // 큐 선언
void bfs(int root){ // root: 시작 노드의 번호
q.push(root); // 시작 노드를 큐에 push
visit[root] = 1; // 방문 여부 기록
while(!q.empty()){ // 큐가 빌 때까지 반복
int cur = q.front(); // 가장 먼저 넣은 노드의 번호 추출
q.pop();
for(int i=0;i<99;i++){
if(node[cur][i] != 0 && visit[i]){
s.push(node[cur][i]); // 다음번 노드를 큐에 push
visit[i] = 1;
}
}
}
return;
}