[Algorithm] 너비 우선 탐색(BFS, Breadth First Search)

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

특정 Data를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 알고리즘

최단 경로를 찾아준다는 점에서 최단 길이를 보장해야할 때 많이 사용되며, Queue를 이용한다.

e.g., 미로 찾기

 

너비 우선 탐색(BFS) Sequence

Step 1: 시작 Node를 큐에 삽입하고 방문 처리

Step 2: Queue에서 하나의 Node를 꺼냄

Step 3: 연결된 Node 중 방문하지 않은 Node를 방문하고 큐에 삽입

Step 4: Step 2로 이동

∴ BFS 수행 순서: 1 2 3 4 5 6 7

 

Code

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

#define MAX 7
int visited[7]; // 방문 유무를 표시할 배열
vector<int> a[8];

void bfs(int start){
    queue<int> q;

    // 시작 노드 큐에 추가
    q.push(start);
    visited[start] = true;

    // 큐가 빌 때까지 반복
    while(!q.empty()){
        int x = q.front(); q.pop();
        cout << x << " ";

        // 현재 큐에서 꺼낸 Node와 인접한 노드 모두 방문
        for(int i=0;i<a[x].size();i++){
            int y = a[x][i];
            // 방문한 적 없는 노드이면 큐에 추가 후 방문 처리
            if(!visited[y]){
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void){
    a[1].push_back(2);
    a[1].push_back(3);

    a[2].push_back(1);
    a[2].push_back(3);
    a[2].push_back(4);
    a[2].push_back(5);

    a[3].push_back(1);
    a[3].push_back(2);
    a[3].push_back(6);
    a[3].push_back(7);

    a[4].push_back(2);
    a[4].push_back(5);

    a[5].push_back(2);
    a[5].push_back(4);

    a[6].push_back(3);
    a[6].push_back(7);

    a[7].push_back(3);
    a[7].push_back(6);

    bfs(1);

    return 0;
}

 

출력

1 2 3 4 5 6 7