알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘

BFS 너비 우선 탐색

 

탐색을 할때 너비를 우선으로 탐색하는 알고리즘

 

BFS 탐색 알고리즘을 통해 '최단 경로'를 찾을 수 있다.

응용하면 미로찾기와 같은 알고리즘도 구현할 수 있다.

 

BFS를 구현하기 위해 큐(Queue)를 사용한다.

1을 큐에 넣는다.

 

1을 큐에서 뺀다. 1과 인접한 2와 3을 큐에 넣는다.

 

2를 큐에서 뺀다. 2와 인접한 4와 5를 큐에 넣는다.

 

3을 큐에서 뺀다. 3과 인접한 6과 7을 큐에 넣는다.

4을 큐에서 뺀다.4와 인접한 8을 큐에 넣는다.

 

5를 뺀다. 5와 인접한 9를 넣는다.

 

 

모든 탐색이 끝나고, 큐에 들어있는 값들은 차례대로 뺀다.

 

그러면, 1 2 3 4 5 6 7 8 9 순으로 탐색이 완료된다.

 

코드 구현

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int number = 9;
int visit[9];
vector<int> a[10];

void bfs(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< a[x].size(); i++){
            int y = a[x][i];
            if(!visit[y]){
                // 방문하지 않았다면..
                q.push(y);
                visit[y] = true; 
            }
        }
    }
}

int main(void){
    
    // 1과 2를 연결 
    a[1].push_back(2);
    a[2].push_back(1);
    
    // 1과 3을 연결 
    a[1].push_back(3);
    a[3].push_back(1);
    
    // 2와 4를 연결 
    a[2].push_back(4);
    a[4].push_back(2);

    // 2와 5를 연결 
    a[2].push_back(5);
    a[5].push_back(2);
    
    // 4와 8을 연결 
    a[4].push_back(8);
    a[8].push_back(4);
    
    // 5와 9를 연결 
    a[5].push_back(9);
    a[9].push_back(5);
    
    // 3과 6을 연결 
    a[3].push_back(6);
    a[6].push_back(3);
    
    // 3과 7을 연결 
    a[3].push_back(7);
    a[7].push_back(3);
    
    // 1번 노드부터 bfs 탐색 실행 
    bfs(1);
    
    return 0;
} 
​

 

 

관련 글

2018/04/30 - [Algorithm] - 알고리즘 :: DFS 깊이 우선 탐색 (C/C++ 구현), 탐색 알고리즘