8. BFS(너비 우선 탐색)

BFS(너비 우선 탐색)

BFS란 너비 우선 탐색을 말합니다. 맹목적인 탐색을 할 때 사용됩니다. BFS는 최단경로를 찾는 문제를 해결할 때도 자주 쓰입니다. 자료구조는 Queue를 사용합니다.

BFS 과정

1. 시작 노드를 큐에 삽입
2. 시작 노드 방문 처리
3. 큐에서 하나의 노드 꺼내기
4. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문 처리 후 차례대로 큐에 삽입

• 위 3~4번 과정을 큐가 빌 때까지 반복

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

using namespace std;

int number = 7;
int visited[8];
vector<int> a[8];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[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 (!visited[y]) {
				q.push(y);
				visited[y] = true;
			}
		}
	}
}

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

	a[2].push_back(1);
	a[2].push_back(3);
	a[2].push_back(4);
	a[2].push_back(5);

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

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

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

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

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

	bfs(1);

	return 0;
}