[Algorithm-Basic]너비 우선 탐색( BFS )

너비 우선 탐색( BFS ) 알고리즘

 

• 선행 개념( 그래프 탐색 )

• 그래프 탐색이란 하나의 정점으로부터 시작해 차례대로 모든 정점( Vertex )을 방문하는 알고리즘이다.

---

• 개념

• 너비 우선 탐색은 그래프 탐색 중, 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다.
• 즉, 루트 노드나 다른 임의의 노드( 시작점 )를 기준으로 해당 노드와 인접한 노드를 우선적으로 방문하는 방식이다.
• 너비 우선 탐색은 '최단 경로'를 기준으로 탐색하기 때문에 '최단 길이'를 보장해야 하는 문제에 사용된다.

---

• 특징

• 재귀적으로 동작하지 않는다.
  • 너비 우선 탐색 알고리즘은 어떤 노드를 방문 했었는지 여부를 반드시 검사하기 때문에 
    이미 방문했던 노드를 재차 방문하여 무한루프에 빠질 위험을 줄인다.
• 큐( queue )를 사용하여 구현한다.
  • 방문 순서대로 저장후, 그 순서 그대로 꺼내는 선입선출( FIFO ) 원칙을 준수한다.

---

• 과정

• 준비물 : 방문할 노드를 담을 큐( Q )
  
  (1) 시작점이 되는 노드 방문 처리 
  (2) 시작점이 되는 노드에 인접한 노드들을 차례로 Q에 담기
  (3) Q에 담긴 노드를 차례로 방문하며 방문처리하고, 
      해당 노드들에 인접한 노드들을 Q에 담기
  ** 해당 과정은 이미 방문한 노드를 제외한 인접 노드를 방문하는 과정에 해당한다.
  (4) 3과정을 더이상 방문할 노드가 없을 때까지 반복
  
  
• 과정의 도식화 : 

---

• 코드( CPP )

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

using namespace std;

int number = 7; //탐색해야 하는 노드의 개수
int c[7]; //방문처리를 위한 배열( checked )
vector<int> v[8]; //각 노드의 인덱스가 1부터 처리될 수 있도록 number+1 개의 배열로 정의 

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

int main(void) {
	//1과 인접한 노드는 2,3 
	v[1].push_back(2);
	v[2].push_back(1);
	 
	v[1].push_back(3);
	v[3].push_back(1);
	
	//2와 인접한 노드는 1,3,4,5
	v[2].push_back(4);
	v[4].push_back(2); 
	
	v[2].push_back(3);
	v[3].push_back(2);
	
	v[2].push_back(5);
	v[5].push_back(2);
	
	//3과 인접한 노드는 1,2,6,7
	v[3].push_back(6);
	v[6].push_back(3);
	
	v[3].push_back(7);
	v[7].push_back(3);
	
	//4와 인접한 노드는 2,5
	v[4].push_back(5);
	v[5].push_back(4);
	
	//6과 인접한 노드는 3,7
	v[6].push_back(7); 
	v[7].push_back(6);
	
	//bfs 수행
	bfs(1);
	
	return 0; 
}