[C++] 너비 우선 탐색(BFS : Breath First Search)

이번 시간에는 너비 우선 탐색에 대해 알아보도록 하겠다.

 

 

 

 

 

 

 

너비 우선 탐색(BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다.

'맹목적인 탐색'을 할 때 사용할 수 있는 탐색 기법으로, '최단 경로'를 찾아준다는 점에서 '최단 길이'를 보장해야할 때  많이 사용한다. 큐를 사용한다.

 

 

 

 

 

 

 

시작점에서부터 가까운 것부터 탐색을 하겠다는 것이다.

맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작한다.

시작 노드를 방문했다고 표시를 해놓고, 그 이후부터 다음의 알고리즘을 반복한다.

 

1. 큐에서 하나의 노드를 꺼낸다.

2. 해당 노드에 연결된 노드들 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

 

 

 

 

 

 

 

 

stl queue를 사용해서 구현해본 코드이다.

 

#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() {
	// 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;
}

 

 

결과는 1 2 3 4 5 6 7이 나온다.

 

 

 

 

 

BFS는 너비를 우선으로 하여 탐색한다는 특징이 중요한 것이고, 이를 이용해 다른 알고리즘에 적용하는 것이 중요한 것이 핵심이다.

 

 

 

 

 

다음 시간에는 깊이 우선 탐색(Depth First Search)에 대해 알아보도록 하겠다.