C++ STL 벡터와 큐로 구현하는 CLRS BFS(너비 우선 탐색) 알고리즘

CLRS(『Introduction to Algorithms』) 교재에서는 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘을 벡터(vector)와 큐(queue)를 사용해 설명합니다. 이 글에서는 해당 알고리즘을 C++ STL을 활용해 직접 구현해 보겠습니다. 먼저 의사코드 형태의 알고리즘을 살펴본 뒤, 실제로 동작하는 C++ 코드와 실행 결과까지 확인하겠습니다.

BFS 알고리즘 (CLRS)

BFS는 시작 정점 s에서 출발해 시작점에 가까운 정점부터 차례대로 넓게 탐색하는 그래프 순회 기법입니다. 각 정점은 색상(color), 시작점으로부터의 거리(d), 선행 정점(p) 속성을 가지며, 큐를 이용해 정점의 발견 순서를 관리합니다.

BFS(G, s)
시작
    G.V - {s}에 속한 각 정점 u에 대해 반복
        u.color := WHITE      // 아직 발견되지 않음
        u.d := ∞              // 거리를 무한대로 초기화
        u.p := NIL            // 선행 정점 없음
    종료
    s.color := GRAY           // 시작 정점을 발견 처리
    s.d := 0
    s.p := NIL
    Q := 빈 큐
    s를 Q에 삽입(enqueue)
    Q가 비어 있지 않은 동안 반복
        u = Q에서 삭제(dequeue)
        u에 인접한 각 정점 v에 대해 반복
            만약 v.color = WHITE이면
                v.color := GRAY
                v.d := u.d + 1
                v.p := u
                v를 Q에 삽입
            종료 if
        종료
        u.color := BLACK      // 정점 u의 탐색 완료
    종료
끝

정점 색상의 의미

• WHITE(흰색): 아직 발견되지 않은 정점
• GRAY(회색): 발견되었지만 인접 정점에 대한 탐색이 아직 끝나지 않은 정점(큐에 존재)
• BLACK(검은색): 자신과 모든 인접 정점에 대한 탐색이 완료된 정점

C++ STL을 이용한 구현 예제

아래 코드는 std::vector로 인접 리스트를 표현하고, std::queue로 BFS의 방문 순서를 관리합니다. 그래프가 여러 개의 연결 요소로 나뉘어 있어도 모든 정점을 방문할 수 있도록 BFSAlgo() 함수에서 미방문 정점을 찾아 BFS를 반복 호출합니다.

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

vector<string> colour;   // 각 정점의 색상(방문 상태)
vector<int> dist;        // 시작 정점으로부터의 거리
vector<int> par;         // BFS 트리에서의 선행(부모) 정점

// 그래프에 간선을 추가하는 함수
void addEdge(vector<int> g[], int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

void BFS(vector<int> g[], int s) {
    queue<int> q;
    q.push(s);                  // 시작 정점을 큐에 삽입
    dist[s] = 0;
    colour[s] = "gray";
    while (!q.empty()) {
        int u = q.front();      // 큐의 맨 앞 요소를 꺼낸 뒤 제거
        q.pop();
        cout << u << " ";
        for (auto i = g[u].begin(); i != g[u].end(); i++) {
            if (colour[*i] == "white") {   // white: 아직 방문하지 않은 정점
                colour[*i] = "gray";       // gray: 방문했지만 탐색 미완료
                dist[*i] = dist[u] + 1;
                par[*i] = u;
                q.push(*i);
            }
        }
        colour[u] = "black";               // black: 탐색이 완료된 정점
    }
}

void BFSAlgo(vector<int> g[], int n) {
    colour.assign(n, "white");   // 모든 정점을 미방문 상태로 초기화
    dist.assign(n, 0);
    par.assign(n, -1);
    for (int i = 0; i < n; i++)
        if (colour[i] == "white")
            BFS(g, i);           // 연결 요소별로 BFS 수행
}

int main() {
    int n = 7;
    vector<int> g[n];
    addEdge(g, 0, 1);
    addEdge(g, 0, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 5);
    addEdge(g, 2, 6);
    BFSAlgo(g, n);
}

실행 결과

0 1 2 3 4 5 6

예제 그래프는 0번 정점을 루트로 하는 트리 구조(간선: 0–1, 0–2, 1–3, 1–4, 2–5, 2–6)이므로, BFS는 시작 정점 0에서부터 레벨 순서대로 정점을 방문하며 위와 같은 출력을 생성합니다.

복잡도 분석

• 시간 복잡도: O(V + E) — 각 정점은 큐에 최대 한 번 삽입되고, 각 간선은 최대 두 번 검사됩니다.
• 공간 복잡도: O(V) — 색상·거리·선행 정점 배열과 큐에 필요한 저장 공간입니다.

참고로 예제 코드의 vector<int> g[n]은 가변 길이 배열(VLA)로 표준 C++에는 포함되지 않으므로, 실무 환경에서는 vector<vector<int>>를 사용하는 것이 더 안전합니다.