[C++] BFS 너비 우선 탐색 알고리즘

너비 우선 탐색 (Breadth - First Search)

개념

BFS(너비우선탐색) : 현재 정점에서 연결된 가까운 점들 부터 탐색

• 가까운 정점 먼저 방문 후 멀리 떨어져 있는 정점 나중에 방문
• 노드를 넓게(wide) 탐색
  • 주로 두 노드 사이 최단 경로 혹은 임의의 경로 찾고 싶을 때 사용
    • 응용하면 미로찾기 같은 알고리즘도 구현 가능

 

BFS 장점

1. 노드 수 적고 깊이 얕은 경우 빠름

2. 단순 검색 속도가 DFS 보다 빠름

3. 너비 우선 탐색하기 때문에 답이 되는 경로가 여러 개인 경우라도 최단 경로임을 보장

4. 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어져도 반드시 최단 경로 찾을 수 있음

 

 

BFS 단점

1. 재귀 호출의 DFS 와 달리 큐에 다음에 탐색할 정점들을 저장해야해 저장 공간 많이 필요

2. 노드 수 늘어나면 탐색해야 하는 노드 많아져 비현실적

3. 해가 존재하지 않는 다면 무한 그래프인 경우 해도 못찾고 , 끝내지도 못함. 유한 그래프인 경우엔 모든 그래프 탐색 후 실패로 끝

 

 

방법

queue에 이웃하는 정점 담아 놓고 차례대로 Pop 하는 방식으로 구현

 

구현

• List 나 vector 통해 구현
• v[] : List(or vector)를 통해서 구현한 그래프
• visit[] : 탐색 여부

 

소스코드

#include <bits/stdc++.h>
// iostream, vecotr ,queue

using namespace std;

const int MAX = 10;
int n,m; // n 정점 개수 ,  m 간선 개수 
vector<int> v[MAX];
int visit[MAX]={0,};

void BFS(int start){
	queue<int> q; // queue 생성
	q.push(start); //초기 시작점 저장 
	visit[start]++;
	
	while( !q.empty() ){
		// 큐에 값이 있다 => 아직 방문하지 않은 노드가 있다.
		int current = q.front();
		cout<<current<<" ";
		q.pop();
		for(int i = 0 ; i < v[x].size();i++){
			int next = v[current][i];
			
			if(!visit[next]){
				visit[next]=1;
				q.push(next);
			}
			
		}	 
	}	
} 

int main(){
	cin >> n >> m;
	
	// 그래프 노드 관계 설정
	for(int i = 0 ; i < m) {
		int a,b;
		cin >> a>> b;
		
		v[a].push_back(b);
		v[b].push_back(a);
		
	}
	BFS();	
	return 0;
}

 

 

 

 

참고

BFS

DFS BFS

위키 BFS

백준 1260

BFS : 큐로 진행과정 설명