너비 우선 탐색(BFS; Breadth-first Search)

너비 우선 탐색은 특정한 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다.

 

즉, 어떠한 시작점이 있을 때 그 시작점과 가까운 것을 우선으로 탐색을 한다.

 

너비 우선 탐색은 큐를 이용하는데, 큐는 먼저 들어온 데이터가 먼저 나간다는 점에서 너비 우선 탐색이 가능하도록 해준다.

너비 우선 탐색(BFS)

 

그림과 같이 큐에서 하나의 노드를 꺼내고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 방문한다.

 

그 후 순서대로 큐에 값을 삽입하는 과정을 반복한다. 그림에 대해 구체적으로 설명하자면,

 

(1) 먼저 큐에서 1을 꺼낸다.

 

(2) 1과 인접한 노드 중 방문하지 않은 2와 3을 방문처리한다.

 

(3) 2를 꺼내고 2와 인접한 노드 중 3은 이미 방문했기 때문에 넘어가고 방문하지 않은 4와 5를 방문처리한다.

 

(4) 3을 꺼내고 3과 인접한 노드 중 방문하지 않은 6과 7을 방문처리한다.

 

(5) 방문처리가 완료되었으며, 남은 노드들 4 5 6 7 을 꺼낸다.

 

(6) 최종적으로 큐에서 꺼낸 순서는 1 2 3 4 5 6 7 이다.

 

  => 이러한 과정을 통해 1부터 가까운 노드들부터 탐색이 이루어진다

 

[예제]

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

using namespace std;

int c[8]; //방문처리
vector<int> a[8];
 
void bfs(int start) {
	queue<int> q;
	q.push(start);
	c[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(!c[y]) {
				q.push(y);
				c[y] = true;
			}
		}
	}
} 

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

 

해당 소스코드는 C++로 작성한 코드이다.

 

큐를 사용하기 위해 헤더에 queue 라이브러리를 정의해준 뒤, 생성한 bfs 함수 내에서 큐를 정의한다.

 

또한 데이터를 저장하기 위해 vector 라이브러리도 헤더에 정의하고 생성한 bfs 함수 내에서 vector를 정의한다.

 

bfs 함수에서 시작점을 받아 큐가 빌 때까지 해당 노드와 인접한 노드 중 방문하지 않은 노드를 방문하고

 

꺼내는 작업을 반복한다.

 

메인코드에서는 각 노드의 정점을 연결해주고 bfs 함수호출 시 시작점 데이터를 전송한다.

 

[결과]

너비 우선 탐색(BFS; Breadth-first search) 결과

 

---

출처

https://blog.naver.com/ndb796/221230944971

15. 너비 우선 탐색(BFS)