[알고리즘 공부] 너비 우선 탐색 (Breath First Search, BFS)

너비 우선 탐색이란? (breath First Search, BFS)

시작 정점을 경계에 추가하는 것으로 시작한다. 경계는 이전에 방문했던 정점들에 의해 구성되고, 현재 경계에 인접한 정점을 반복적으로 탐색한다. BFS의 중요한 특징은, 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문한다는 점이다.

이를 구현할 때에는, 보통 경계를 별도의 자료구조로 만들어 명시적으로 사용하지 않고, 대신 정점 ID를 큐(Queue)에 저장하여 시작 정점과 가까운 정점을 멀리 있는 정점보다 먼저 방문할 수 있도록 구현한다.

다음은 너비 우선 탐색을 표현한 애니메이션이다.

너비 우선 탐색

두 애니메이션을 보면 그래프를 탐색함에 있어 무조건 같은 Level의 부모 정점들이 먼저 탐색되고, 그 다음 Level에 있는 자식 정점들이 나중에 탐색되는 모습을 보인다.

BFS의 장점:

1. 출발 정점에서 목표 정점까지의 최단경로를 보장한다. (단, 가중치가 없는 그래프 한정. 가중치가 있는 그래프는 다익스트라 등 다른 알고리즘을 활용하여 최단경로를 찾아내야 한다.)

BFS의 단점:

1. 경로가 매우 길면, 탐색 경계가 급격히 증가하기 때문에 Space-Complexity가 커지게 된다.
2. 경로가 존재하지 않으면, 유한 그래프의 경우 모든 경우의 수를 탐색한 뒤 종료하게 된다.

이는 DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.

---

다음은 실제로 너비 우선 탐색을 구현해보자. BFS는 재귀 호출(Recursion Call)을 이용하여 소스 코드로 구현하는 DFS와는 달리, 자료 구조 Queue를 사용하는 경우가 일반적이다.

구현에 사용될 그래프는 다음과 같다. 이전 게시글에서 사용한 그래프와 똑같은 그래프를 사용해보자.

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

using namespace std;

bool visited[9];
vector<int> Graph[9];

// BFS 함수 정의
void BFS(int start) {
    queue<int> q;
    q.push(start); //첫 노드를 queue에 삽입
    visited[start] = true; //첫 노드를 방문 처리

    //큐가 빌 때까지 반복
    while (!q.empty()) {
        int n = q.front();
        q.pop();
        cout << n << ' ';
        //큐에서 하나의 정점을 뽑아 출력

        for (int i = 0; i < Graph[n].size(); i++) {     //인접한 정점의 갯수만큼 탐색
            int idx = Graph[n][i];

            if (!visited[idx]) {        //아직 방문하지 않은 정점일때에만 진행. 방문했던 정점은 무시하고 다른 정점을 찾음
                q.push(idx);
                visited[idx] = true;    //아직 방문하지 않은 정점들을 큐에 삽입 후, 방문 처리
            }
        }
    }
}

int main() {
    Graph[1].push_back(2);
    Graph[1].push_back(5);

    Graph[2].push_back(1);
    Graph[2].push_back(4);
    Graph[2].push_back(5);

    Graph[3].push_back(4);
    Graph[3].push_back(7);

    Graph[4].push_back(2);
    Graph[4].push_back(3);
    Graph[4].push_back(5);
    Graph[4].push_back(6);
    Graph[4].push_back(8);

    Graph[5].push_back(1);
    Graph[5].push_back(2);
    Graph[5].push_back(4);
    Graph[5].push_back(8);

    Graph[6].push_back(4);
    Graph[6].push_back(7);
    Graph[6].push_back(8);

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

    Graph[8].push_back(4);
    Graph[8].push_back(5);
    Graph[8].push_back(6);
    //vector 배열로 그래프 정의

    BFS(1);

    return 0;
}

이해하기 쉽게 수행한 시퀀스대로 색깔을 다르게 나누어 봤다. BFS라는 같은 알고리즘을 기반으로 그래프를 탐색한 것이기 때문에 실제 코드에서 수행한것과 똑같은 결과값이 나온다.