C++ 비연결 그래프에서의 너비 우선 탐색(BFS) 구현 방법

비연결 그래프(disconnected graph)란 하나 이상의 정점이 다른 정점들과 어떤 경로로도 연결되어 있지 않은 그래프를 말합니다. 즉, 그래프 전체가 여러 개의 연결 요소(connected component)로 나뉘어 있는 경우입니다.

위 그림처럼 비연결 그래프에서는 특정 정점에서 출발해도 도달할 수 없는 정점들이 존재합니다.

일반 BFS가 동작하지 않는 이유

기본적인 BFS(너비 우선 탐색)는 그래프가 연결 그래프, 즉 임의의 한 정점에서 출발했을 때 나머지 모든 정점에 도달할 수 있는 경우에만 올바르게 동작합니다. 시작 정점 하나에서 BFS를 한 번만 수행해도 도달 가능한 모든 정점을 방문할 수 있기 때문입니다.

그러나 비연결 그래프에서는 단 한 번의 BFS 호출만으로는 도달할 수 없는 정점들이 남게 됩니다. 따라서 그래프의 모든 정점을 빠짐없이 탐색하려면 알고리즘을 수정해야 합니다.

해결 아이디어: 모든 정점에서 BFS 시도하기

핵심은 간단합니다. 그래프의 모든 정점을 차례대로 확인하면서, 아직 방문하지 않은 정점을 발견할 때마다 그 정점을 새로운 시작점으로 삼아 BFS를 수행하는 것입니다. 이렇게 하면 각 연결 요소마다 한 번씩 BFS가 실행되므로, 그래프가 몇 개의 부분으로 나뉘어 있더라도 모든 정점을 빠짐없이 방문할 수 있습니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

void insertnode(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
}

void breathFirstSearch(int u, vector<int> adj[], vector<bool> &visited) {
    list<int> q;
    visited[u] = true;
    q.push_back(u);
    while (!q.empty()) {
        u = q.front();
        cout << u << " ";
        q.pop_front();
        for (int i = 0; i != adj[u].size(); ++i) {
            if (!visited[adj[u][i]]) {
                visited[adj[u][i]] = true;
                q.push_back(adj[u][i]);
            }
        }
    }
}

void BFSdisc(vector<int> adj[], int V) {
    vector<bool> visited(V, false);
    for (int u = 0; u < V; u++)
        if (visited[u] == false)
            breathFirstSearch(u, adj, visited);
}

int main() {
    int V = 5;
    vector<int> adj[V];
    insertnode(adj, 0, 4);
    insertnode(adj, 1, 2);
    insertnode(adj, 1, 3);
    insertnode(adj, 1, 4);
    insertnode(adj, 2, 3);
    insertnode(adj, 3, 4);
    BFSdisc(adj, V);
    return 0;
}

실행 결과

0 4 1 2 3

코드 동작 설명

insertnode(): 인접 리스트(adjacency list) 형태로 그래프의 간선을 추가하는 함수입니다.
breathFirstSearch(): 큐(list)를 사용하여 시작 정점 u부터 인접한 정점들을 너비 우선으로 방문합니다. 방문 여부는 visited 배열로 관리하여 같은 정점이 중복 처리되지 않도록 합니다.
BFSdisc(): 이 예제의 핵심 함수입니다. 0번부터 V-1번까지 모든 정점을 순서대로 확인하며, 아직 방문하지 않은 정점을 만나면 그 정점에서 새로운 BFS를 시작합니다.

예제 그래프에서 정점 0과 4는 서로 연결된 하나의 연결 요소를 이루고, 정점 1, 2, 3은 또 다른 연결 요소를 이룹니다. 따라서 첫 번째 BFS는 정점 0에서 시작해 0 4를 출력하고, 두 번째 BFS는 정점 1에서 시작해 1 2 3을 출력합니다.

시간 및 공간 복잡도

각 정점과 간선은 최대 한 번씩만 처리되므로 전체 시간 복잡도는 O(V + E)이며, 방문 배열과 큐에 사용되는 공간 복잡도는 O(V)입니다. 이 방식은 그래프가 연결되어 있든 아니든 항상 모든 정점을 빠짐없이 탐색할 수 있다는 장점이 있습니다.