[자료구조] 너비 우선 탐색(BFS)

BFS는 너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘이다. 

 

자 또 그림을 한번 보자.

 

 

DFS 할 때와 같은 그래프이다. 위 그림과 같이 BFS 는 큐를 사용하고 방문 후 숫자를 큐에 저장한다. 그 후 enqueue 된 숫자가 dequeue 되면서 연결된 다음 숫자를 enqueue 해준다.

 

아래는 코드이다.

 

 

#include <stdio.h>
#include <queue>
#include<vector>

using namespace std;

bool visited[9];
vector<int> graph[9];

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 < graph[x].size(); i++) {
			int y = graph[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
			}
		}
	}
}

int main() {
	graph[1].push_back(2);
	graph[1].push_back(6);
	graph[1].push_back(7);

	graph[2].push_back(1);
	graph[2].push_back(8);

	graph[3].push_back(8);

	graph[4].push_back(8);

	graph[5].push_back(6);
	graph[5].push_back(7);

	graph[6].push_back(1);
	graph[6].push_back(5);

	graph[7].push_back(5);
	graph[7].push_back(1);

	graph[8].push_back(3);
	graph[8].push_back(4);

	BFS(1);
}