DFS에 이어, BFS는 넓이를 우선탐색하는 것으로서, 스케줄링 기법에서는 FIFO(First In First Out)방식을 통해 구현한다.
큐(Queue)에 다음에 구현될 노드를 저장하고, 차례대로 구현하는 방식을 따르는 것이다
BFS(Breadth First Search, 너비우선탐색)란 루트 노드로부터 인접한 노드를 먼저 탐색하는 방법을 말한다.
동일 Level 내의 인접 노드를 먼저 탐색하고, 그 다음에 상위 Level로 진입하여 탐색한다.
DFS와 달리, BFS의 장점은 무엇일까?
BFS는 인접노드를 먼저 탐색하기 때문에, 최단경로를 찾는 부분에 있어 유리하다고 볼 수 있다.
DFS의 경우, 1 → 2 → 5 → 6의 형태로 탐색하기 때문에, A와 가까운 노드를 탐색하기 보다는 전체 경로의 가짓 수를 찾는 부분에서 더 유리하다고 볼 수 있다
BFS의 경우 2,3,4를 먼저 탐색하기 때문에, 처음 노드로부터 최단경로 가짓수를 찾는 부분에서 더 유리하다.
앞에서, 말했듯이 BFS를 구현할 때, 재귀(Recursion)를 사용하여 구현할 수도 있지만, 복잡성을 고려하여 Queue를 사용하는 것이 일반적이다.
위의 Queue에서는 A를 실행하면서, 동시에 뒤에 다음에 실행할 B,C,D를 예약리스트에 넣어, 순차로 처리하는 방식을 따른다.
전부 다 실행이 되면, 결국 HEAD와 TAIL이 겹치고 모두 탐색을 하게 되어 인접 노드를 우선탐색하게 된다.
위의 그림을 구현하면 다음과 같다.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<vector<int>> alist = { {1,2,3},{4,5},{},{},{},{} }; //ⓐ 위의 그림을 하드코딩
int queue[6] = { 0 }; // ⓑ FIFO 스케줄러를 구현할 queue 배열 선언, head index의 값은 0부터 시작
string str = "ABCDEF"; // ⓒ 노드 index에 해당하는 문자
int main (){
int head = 0; // ⓓ 초기 세팅 시, head는 0번부터, tail은 1번부터 시작
int tail = 1;
while (head != tail) {
int now = queue[head];
cout << str[now]; //ⓔ head의 값을 출력하며 시작 -> 반복되면서 다음 값을 출력함
// head의 역할은 현재 출력하는 값이라고 보면 편함
for (int i = 0; i < alist[now].size(); i++) {
int next = alist[now][i];
queue[tail++] = next; //ⓔ 다음 head에서 실행할 값을 예약해주는 과정(next)로 표현
// for문을 돌면서, 이어져있는 모든 값을 queue에 예약해줌과 동시에
// tail을 한 칸씩 뒤로 민다.
}
head++;
}
return 0;
}위의 방식은 표준 C++ 라이브러리 (STL, Standard Template Library)을 사용하면 더 쉽게 구현할 수도 있다.
또한, Level 변수를 추가하여, 현재 어느 Level을 탐색하는 지까지 알 수가 있다.
다음 예시를 보자.
#include <iostream>
#include <vector>
#include <string>
#include <queue>; // QUEUE의 라이브러리 등록
using namespace std;
struct Node {
int n;
int level;
};
vector<vector<int>> alist = { {1,2,3},{4,5},{},{},{},{} };
string str = "ABCDEF";
queue<Node> q;
int main (){
q.push({ 0,0 }); //초기에 Head를 선언하지 않고, Head와 Level 값을 넣음
while (!q.empty()) {
Node now = q.front(); // queue의 맨처음 값을 now 변수에 넣음
q.pop(); // queue의 맨처음 값을 지움 (앞줄에서 읽었으니 지움)
cout << "값: " << str[now.n] << ", Level:" << now.level << '\n';
for (int i = 0; i < alist[now.n].size(); i++) {
int next = alist[now.n][i];
q.push({ next, now.level + 1 }); // 다음 실행할 queue에 next값과, 다음 level을 넣음
}
}
return 0;
}