너비우선탐색(BFS)

너비우선탐색(Breadth first search, BFS)은 탐색을 할때 너비를 우선으로 탐색하는 기법이다.

BFS는 '맹목적인 탐색 기법'에 속하며 '최단 경로'를 보장해줍니다. 또한, BFS는 자료구조인 Queue(FIFO)에 기반하여 구현할 수 있습니다.

 

코드는 아래와 같은 그래프를 기준으로 작성하였다.

 

1~7 노드로 이루어진 그래프

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n;
int flag[8];
vector<int> bfs[8];
queue<int> q;

void bfs_search(int start) {
	q.push(start);
	flag[start] = true;

	while (!q.empty()) {
		int x = q.front();
		printf("%d ", x);
		q.pop();
		for (int i = 0; i < bfs[x].size(); i++) {
			int y = bfs[x][i];
			if (!flag[y]) {
				q.push(y);
				flag[y] = true;
			}

		}
	}

}

int main() {
	bfs[1].push_back(2);
	bfs[1].push_back(3);

	bfs[2].push_back(3);
	bfs[2].push_back(4);
	bfs[2].push_back(5);

	bfs[3].push_back(6);
	bfs[3].push_back(7);
	bfs[3].push_back(1);
	bfs[3].push_back(2);

	bfs[4].push_back(2);
	bfs[4].push_back(5);

	bfs[5].push_back(2);
	bfs[5].push_back(4);

	bfs[6].push_back(3);
	bfs[6].push_back(7);
	
	bfs[7].push_back(6);
	bfs[7].push_back(3);

	bfs_search(1);

}