[알고리즘]C++ BFS 구현하기

BFS(Breath First Search)는 말그대로 너비를 우선 탐색한다.

DFS는 연결된 노드를 계속 들어가며 재귀호출하는 방식이었지만

BFS는 이와 달리 queue를 이용해서 루트노드에 연결되어있는 모든 노드를 다 탐색 후에 다음 깊이로 들어간다.

소스로 확인하면 다음과 같다.

#include<iostream>
#include<queue>
using namespace std;
int map[10][10]={0};
int visit[10]={0};
queue<int> q;
int num;
 
void bfs(int v){
    cout<<v<<" ";
    q.push(v);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(int i=0;i<num;i++){
            if(map[node][i]==1 && visit[i]==0){
                visit[node]=1;
                cout<<i<<" ";
                q.push(i);
            }
        }
    }
}
int main(){
    cin>>num;
    while(1){
        int v1,v2;
        cin>>v1>>v2;
        if(v1==-1&&v2==-1)
            break;
        map[v1][v2]=map[v2][v1]=1;
    }
    bfs(1);
    return 0;
}

위와같이 노드의 개수를 입력받고 -1,-1 을 입력하기 전까지 모든 노드를 입력받는다.

map이라는 배열을 통해 두 노드가 연결되어있으면 쌍방연결로 간주하고 map[v1][v2]=1로 입력한다.

bfs함수에서는 첫 시작 노드를 출력하고 q에 push해준다.

이후에 q가 비어있을때까지 while반복문을 통해 모든

노드를 탐색한다.

이때 q에서 한 노드를 꺼내 그 노드를 기준으로 나머지 모든 노드를 탐색한다.

map배열로 연결되어있으면서 방문하지 않았던 노드가 있으면 해당 노드를 출력하고 q에 push한다.

이를 q가 비어있을때까지 반복하면 BFS방식으로 모든 노드를 탐색할 수 있다.

                                    

위와같이 연결된 그래프를 오른쪽 입력을 통해 구성하였다. 

BFS방식을 적용하면 1 2 3 4 5 6 7 8 순서로 출력이 될 것이고 오른쪽 결과와 같이 잘 출력됨을 알 수 있다.

그래프출처 : swexpertacademy