그래프 너비 우선 탐색(BFS) 완벽 정리: 개념, 알고리즘, C++ 구현까지

너비 우선 탐색(Breadth First Search, BFS)은 주어진 그래프의 모든 노드를 방문하기 위해 사용되는 대표적인 그래프 순회 알고리즘입니다. BFS는 시작 노드 하나를 선택한 뒤, 해당 노드에 인접한 모든 노드를 차례대로 방문하는 방식으로 동작합니다. 인접한 정점들을 모두 처리하고 나면, 다음 정점으로 이동하여 그 정점의 인접 정점들을 다시 확인합니다.

BFS의 핵심 원리

BFS를 구현하려면 큐(Queue) 자료구조가 반드시 필요합니다. 현재 정점에 인접한 모든 정점을 큐에 추가하고, 인접 정점 처리가 끝나면 큐에서 하나의 항목을 꺼내 해당 정점을 기준으로 다시 탐색을 시작합니다. 이러한 선입선출(FIFO) 방식 덕분에 시작점에서 가까운 노드부터 멀리 있는 노드까지 순서대로 탐색할 수 있습니다.

또한 그래프에는 순환(cycle)이 존재할 수 있으므로, 이미 방문한 노드를 다시 방문하지 않도록 배열을 사용해 각 노드의 방문 여부를 표시해야 합니다. 이 과정이 없으면 무한 루프에 빠질 위험이 있습니다.

입력과 출력

입력:
그래프의 인접 행렬(Adjacency Matrix)

      A B C D E F
   A  0 1 1 1 0 0
   B  1 0 0 1 1 0
   C  1 0 0 1 0 1
   D  1 1 1 0 1 1
   E  0 1 0 1 0 1
   F  0 0 1 1 1 0

출력:
BFS Traversal: B A D E C F

알고리즘 의사코드

아래는 BFS 알고리즘의 의사코드입니다.

bfs(vertices, start)

입력 − 정점 목록과 시작 정점

출력 − 그래프가 연결되어 있다면 모든 노드를 순회

Begin
    빈 큐 que를 생성한다
    처음에 모든 노드의 상태를 '미방문'으로 표시한다
    시작 정점을 que에 추가한다

    while que가 비어있지 않은 동안 반복:
        que에서 항목을 삭제하고 u에 저장한다
        정점 u를 출력한다

        u와 인접한 모든 정점 i에 대해:
            if vertices[i]가 미방문 상태라면:
                vertices[i]를 '임시 방문'으로 표시한다
                v를 큐에 추가한다
            mark
        done

        u를 '완전 방문' 상태로 표시한다
    done
End

C++ 구현 예제

다음은 인접 행렬로 표현된 그래프에서 BFS를 수행하는 C++ 코드입니다. 노드의 상태는 0(미방문), 1(방문), 2(처리 완료)로 관리됩니다.

#include<iostream>
#include<queue>
#define NODE 6
using namespace std;

typedef struct node {
    int val;
    int state;     // 상태 (0: 미방문, 1: 방문, 2: 완료)
}node;

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0, 0},
    {1, 0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0, 1},
    {1, 1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 1, 0}
};

void bfs(node *vert, node s) {
    node u;
    int i, j;
    queue<node> que;

    for(i = 0; i<NODE; i++) {
        vert[i].state = 0;     // 미방문 상태로 초기화
    }

    vert[s.val].state = 1;     // 시작 노드 방문 처리
    que.push(s);               // 시작 노드를 큐에 삽입

    while(!que.empty()) {
        u = que.front();       // 큐에서 제거하며 출력
        que.pop();
        cout << char(u.val+'A') << " ";

        for(i = 0; i<NODE; i++) {
            if(graph[i][u.val]) {
                // 아직 방문하지 않은 노드인 경우
                if(vert[i].state == 0) {
                    vert[i].state = 1;
                    que.push(vert[i]);
                }
            }
        }
        u.state = 2;           // 노드 u 처리 완료
    }
}

int main() {
    node vertices[NODE];
    node start;
    char s;

    for(int i = 0; i<NODE; i++) {
        vertices[i].val = i;
    }

    s = 'B';                   // 시작 정점 B
    start.val = s-'A';
    cout << "BFS Traversal: ";
    bfs(vertices, start);
    cout << endl;
}

실행 결과

BFS Traversal: B A D E C F

마무리

BFS는 최단 경로 탐색, 연결 요소 검사, 레벨 순서 순회 등 다양한 문제에 활용되는 필수 알고리즘입니다. 시간 복잡도는 인접 행렬 기준 O(V²), 인접 리스트 기준 O(V+E)이며, 공간 복잡도는 O(V)입니다. 큐와 방문 배열이라는 두 가지 핵심 도구만 이해하면 누구나 쉽게 구현할 수 있으니, 위 예제 코드를 직접 실행해 보며 동작 원리를 익혀보시기 바랍니다.