너비 우선 탐색(Breath First Search) - BFS 에 대해 알아보자

  

블로그 https://blog.naver.com/ndb796/221230944971 와 https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/ 을 참고하였습니다. 

1. BFS (Breath First Search) - 너비 우선 탐색 이란??

  - 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법으로 깊게 탐색하기 전 넓게 탐색 하는 알고리즘입니다.

  - Queue를 사용하며, 시작노드에서 거리에 따라단계별로 탐색합니다.

2. BFS의 과정

  ① 9개의 노드들이 존재합니다.

  ② 노드 1을 시작 노드로 큐에 삽입하며 시작합니다.

  ③ 노드 1에 연결되는 노드2와 3을 차례대로 큐에 삽입합니다.

 

  ④ Queue의 2 노드를 방문하지만 연결된 노드가 없으므로 Queue에 삽입하지 않습니다.

  ⑤ 3의 노드를 방문하고, 연결된 노드 4와 5를 Queue에 삽입합니다.

  ⑥ 4의 노드를 방문하고, 4와 인접한 7, 8, 6의 노드들을 Queue에 삽입합니다.

  ⑦ 5의 노드를 방문하고 인접한 노드인 9을 Queue에 삽입합니다.

  ⑦ 노드 7을 방문하며 위의 방법들로 각각의 노드들을 Queue에서 차례대로 꺼냅니다.

  ※ 처음  시작 노드를 저장하며, 이웃한 노드들을 방문합니다. 

     이후 Queue에서 꺼낸 노드들의 인접한 노드들을 방문하며 Queue에 노드를 삽입하고, Queue가 소진될때까지 계속합니다.

3. BFS 구현

 #include <iostream>
 #include <queue>
 #include <vector>
 
 using namespace std;
 
 int number=9; // 노드의 개수 
 int c[9]; // 방문처리를 위한 배열 
 vector<int> a[10]; 
 
 void bfs(int start) {
     queue<int> q;
     q.push(start); // queue의 시작점을 넣는다. 
     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]) { // 방문을 하지 않은 상태라면 queue에 삽입. 
                  q.push(y);
                  c[y] = true; 
             }
         }
     }
 }
 
 int main(void) {
     a[1].push_back(2);
     a[2].push_back(1);
     
     a[1].push_back(3);
     a[3].push_back(1);
     
     a[3].push_back(4);
     a[4].push_back(3);
     
     a[3].push_back(5);
     a[5].push_back(3);
     
     a[4].push_back(7);
     a[7].push_back(4);
     
     a[4].push_back(8);
     a[8].push_back(4);
     
     a[4].push_back(6);
     a[6].push_back(4);
     
     a[5].push_back(9);
     a[9].push_back(5);
     
     bfs(1);
 }

▶ 결과화면