[기본문제풀이] BFS 너비우선탐색

 

풀이 일시 : 2020-08-30

​

 

BFS :

탐색 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것. 그 중 한 방법인 너비우선탐색은 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 시작정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문한다.

DFS와 비교하여 wide 하게 탐색하는 BFS는 queue를 이용하여 구현할 수 있다.

최단거리를 구할때 주로 이용된다.

 

​

 

문제 :

BFS를 queue로 구현하라.

​

 

풀이 :

인접 노드들을 queue에 담고 그 다음 노드는 큐에서 나오는 노드가 될 것이다. 그 노드의 인접노드를 다시 queue에 넣는 작업을 queue가 비기 전 까지 반복해준다.

#include <iostream>
#include <queue>
#include <vector>
#define MAX 101

using namespace std;
vector <int> a[MAX];
int d[MAX] = { 0, };

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


int main() {

	a[1].push_back(2);
	a[2].push_back(1);

	a[1].push_back(3);
	a[3].push_back(1);

	a[1].push_back(8);
	a[8].push_back(1);

	a[2].push_back(7);
	a[7].push_back(2);

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

	a[7].push_back(8);
	a[8].push_back(7);

	a[3].push_back(4);
	a[4].push_back(3);

	a[3].push_back(5);
	a[5].push_back(3);

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

	bfs(1);
	return 0;
} 

 

 

추가자료 : [개념정리] 큐 (queue)

dbstndi6316.tistory.com/48?category=953968

[기본문제풀이] queue

dbstndi6316.tistory.com/27?category=953970

[개념정리] queue