너비 우선 탐색. Breadth-first search(BFS)

 

- 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법.

- 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

- 큐를 이용해서 구현

- 미로 찾기 알고리즘에서 주로 이용함

 

 

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

using namespace std;

int number = 7;
int c[8]; // check 처리 확인 배열
vector<int> v[8];

void bfs(int start){
	queue<int> q;
	q.push(start); // queue에 시작점 넣고,
	arr[start] = true; // 방문 처리
	
	while(!q.empty()){
		int x = q.front();
		q.pop();
		cout << x << ' ';
		
		for(int i = 0; i < v[x].size(); i++){
			int y = v[x][i];
			if(!c[y]){ // checked가 아니라면
				q.push(y); // 넣고
				c[y] = true; // 방문 체크
			}
		}
	}
}

int main() { 
	// 1과 2을 연결 
	v[1].push_back(2); 
	v[2].push_back(1); 
	
	// 1과 3을 연결 
	v[1].push_back(3); 
	v[3].push_back(1); 
	
	// 2와 3을 연결 
	v[2].push_back(3); 
	v[3].push_back(2); 
	
	// 2와 4을 연결 
	v[2].push_back(4); 
	v[4].push_back(2); 
	
	// 2와 5를 연결 
	v[2].push_back(5); 
	v[5].push_back(2); 
	
	// 3과 6을 연결 
	v[3].push_back(6);
	v[6].push_back(3); 
	
	// 3과 7을 연결 
	v[3].push_back(7); 
	v[7].push_back(3); 
	
	// 4과 5을 연결 
	v[4].push_back(5);
	v[5].push_back(4); 
	
	// 6과 7을 연결 
	v[6].push_back(7); 
	v[7].push_back(6); 
	
	bfs(1);

	return 0;
}

 

 

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

15. 너비 우선 탐색(BFS)