[3][그래프 이론] - 너비 우선 탐색 BFS (Breadth-First Search)

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

너비 우선 탐색 (이하 BFS) 는 시작 정점에서 방문할 수 있는 정점들을 우선 방문한후, 이후에 그 정점들에서 방문 할수 있는 정점들을 방문 하는 탐색 방법이다.

 

 

예를 들어 위와같은 그래프에서 0번 정점으로 부터 BFS를 시행한다고 하면 ( 방문할수 있는 정점이 여러개라면 번호가 낮은 정점을 우선 방문한다고 가정 )

 

이전의 DFS에서는 1번 정점을 방문한뒤, 1번 정점에서 방문할 수 있는 2번 정점을 방문하였지만

 

BFS에서는 1번 정점을 방문한뒤, 바로 9번 정점을 방문한다.

 

이후 1번 정점에서 방문할 수 있는 2,5,7번 정점을 방문한 후, 9번 정점에서 방문할 수 있는 정점을 방문한다. ( 위 그래프 상황에서는 이미 9번과 연결된 7번 정점을 1번 정점에서 방문했으므로 방문하지 않는다 )

 

따라서 아래와 같이 방문을 하게된다.

 

아래에서

분홍색 정점은 현재 방문을 해서 해당 정점에서 다음 정점으로 방문을 해볼 필요가 있는 정점들이다.

노란색 정점은 이제 막 방문한 정점을 의미한다.

연두색 정점은 방문이 완료되고, 해당정점에서 나아갈 수 있는 정점의 방문까지 완료된 정점들이다.

 

 

재귀로 해결이 가능했던 DFS와는 다르게 BFS에서는 미리 정점들을 방문하고, 이후에 그 정점들의 다음 정점들을 방문해야하므로 큐(queue)가 필요하다.

 

vector<vector<int> > graph;
queue<int> q1;
queue<int> q2;

int visited[10]; // 0 - 미방문 / 1 - 방문

void bfs(){
    int now;
    int len;
    q1 = q2;
    while(q2.size() > 0){
        q2.pop();
    }
    len = q1.size();
    if(len > 0){
        for(int i=0;i<len;i++){
            now = q1.front();
            q1.pop();
            cout << "visit " << now << endl;
            for(int j=0; j<graph[now].size(); j++){
                if(visited[graph[now][j]] == 0){
                    q2.push(graph[now][j]);
                    visited[graph[now][j]] = 1;
                }
            }

        }
        bfs();
    }
}

 

따라서 위와같이 queue를 선언해주었고 q1은 직전에 방문을 한 정점이며, q2는 현재 방문한 정점들을 누적하는 큐이다.

 

따라서 bfs()가 실행되면 현재 방문한 정점들의 다음 정점으로 나아가야 하기에 q2를 q1으로 변경시켰다.

 

 

다음은 c++로 작성된 BFS 전체 코드이다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int> > graph;
queue<int> q1;
queue<int> q2;

int visited[10]; // 0 - 미방문 / 1 - 방문

void bfs(){
    int now;
    int len;
    q1 = q2;
    while(q2.size() > 0){
        q2.pop();
    }
    len = q1.size();
    if(len > 0){
        for(int i=0;i<len;i++){
            now = q1.front();
            q1.pop();
            cout << "visit " << now << endl;
            for(int j=0; j<graph[now].size(); j++){
                if(visited[graph[now][j]] == 0){
                    q2.push(graph[now][j]);
                    visited[graph[now][j]] = 1;
                }
            }

        }
        bfs();
    }
}

int main(){
    for(int i=0;i<10;i++){
        graph.push_back(vector<int>());
        visited[i] = 0;
    }
    graph[0].push_back(1);
    graph[0].push_back(9);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[1].push_back(5);
    graph[1].push_back(7);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(2);
    graph[4].push_back(2);
    graph[5].push_back(2);
    graph[5].push_back(6);
    graph[5].push_back(1);
    graph[7].push_back(1);
    graph[7].push_back(8);
    graph[7].push_back(9);
    graph[8].push_back(7);
    graph[9].push_back(0);
    graph[9].push_back(7);

    q2.push(0);
    visited[0] = 1;

    bfs();
}

 

최종적으로 다음과같이 출력이된다.