[Algorithm] 너비 우선 탐색(Breath First Search)

너비 우선 탐색(BFS)이란?

너비 우선 탐색(이하 BFS)는 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 즉 깊게 탐색하기 전에 같은 레벨의 노드를 다 방문하고 넘어간다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

탐색 과정

1. 시작노드를 먼저 방문한다.
   • 방문한 노드는 체크한다.
   • 큐에 방문된 노드를 삽입한다.
2. 큐에서 꺼낸 노드와 인접한 모든 노드들을 방문한다.
   • 마찬가지로 방문한 노드에 체크해준다.
   • 큐에 방문된 노드를 삽입한다.
3. 큐가 empty할 때까지 계속 반복한다.

구현

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int number = 5;		// 노드의 개수
int check[5];		// 방문한 노드를 체크
vector<int> a[6];	// 노드를 저장할 큐

// 시작 노드를 매개변수로 받아준다.
void bfs(int start) {
	queue<int> q;
	q.push(start);
	check[start] = true;

	cout << "탐색 결과 : ";

	while (!q.empty()) {	// 큐에 있는 모든 노드를 탐색할 때까지 계속 반복해준다.
		int x = q.front();
		q.pop();
		cout << x << " ";
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (!check[y]) {
				q.push(y);
				check[y] = true;
			}
		}
	}
}

int main() {
	// 0과 1을 연결
	a[0].push_back(1);
	a[1].push_back(0);

	// 0과 2를 연결
	a[0].push_back(2);
	a[2].push_back(0);

	// 0과 4을 연결
	a[0].push_back(4);
	a[4].push_back(0);

	// 1과 2를 연결
	a[1].push_back(2);
	a[2].push_back(1);

	// 2와 3을 연결
	a[2].push_back(3);
	a[3].push_back(2);

	// 3과 4를 연결
	a[3].push_back(4);
	a[4].push_back(3);

	// 2와 4를 연결
	a[2].push_back(4);
	a[4].push_back(2);

	bfs(0);

	return 0;
} 

출력 결과

탐색 결과 : 0 1 2 4 3

참고

참고