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

세상의 모든 알고리즘 - BFS

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

 

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

 가까운곳 먼저 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

 

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우

깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.

 

너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

 

너비 우선 탐색(BFS)의 특징

• 직관적이지 않은 면이 있다.
• 재귀적으로 동작하지 않는다. 
• 그래프 탐색과의 차이점은 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다.
• 차례대로 저장하고 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.

---

void BFSSolution_1(int start)
{
 
queue<int> q;
    q.push(start);
    visit[start] = true;
   
    while(!q.empty()){
        // 큐에 값이 있을경우 계속 반복 실행
        // 큐에 값이 있다. => 아직 방문하지 않은 노드가 존재 한다.
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for(int i=0; i< ab[x].size(); i++){
            int y = ab[x][i];
            if(!visit[y]){
                // 방문하지 않았다면..
                q.push(y);
                visit[y] = true;
            }
        }
    }
// 1과 2를 연결
ab[1].push_back(2);
ab[2].push_back(1);
   
// 1과 3을 연결
ab[1].push_back(3);
ab[3].push_back(1);
   
// 2와 4를 연결
ab[2].push_back(4);
ab[4].push_back(2);
 
// 2와 5를 연결
ab[2].push_back(5);
ab[5].push_back(2);
   
// 4와 8을 연결
ab[4].push_back(8);
ab[8].push_back(4);
   
// 5와 9를 연결
ab[5].push_back(9);
ab[9].push_back(5);
   
// 3과 6을 연결
ab[3].push_back(6);
ab[6].push_back(3);
   
// 3과 7을 연결
ab[3].push_back(7);
ab[7].push_back(3);
   
// 1번 노드부터 bfs 탐색 실행
// BFSSolution(1);
 
⁠
//bfs Solution Test
 
 
int number = 9;
int visit[9];
vector<int> ab[10];
 

void BFSSolution_2(int start)
{
 
queue<int> q;
    q.push(start);
    visit[start] = true;
   
    while(!q.empty()){
        // 큐에 값이 있을경우 계속 반복 실행
        // 큐에 값이 있다. => 아직 방문하지 않은 노드가 존재 한다.
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for(int i=0; i< ab[x].size(); i++){
            int y = ab[x][i];
            if(!visit[y]){
                // 방문하지 않았다면..
                q.push(y);
                visit[y] = true;
            }
        }
    }
}