C++로 BFS를 활용해 방향 그래프의 연결성 확인하기

그래프의 연결성을 확인하려면 임의의 그래프 탐색 알고리즘을 사용해 모든 노드를 한 번씩 순회해 봅니다. 탐색이 끝난 후에도 방문하지 않은 노드가 하나라도 남아 있다면, 해당 그래프는 연결 그래프가 아니라고 판단할 수 있습니다.

방향 그래프(directed graph)에서는 연결성을 확인하기 위해 모든 노드를 시작점으로 삼아 탐색을 수행해야 합니다. 어떤 노드는 나가는 간선(outgoing edge)만 있고 들어오는 간선(incoming edge)이 전혀 없을 수 있기 때문에, 다른 노드에서 출발한 탐색만으로는 그 노드를 결코 방문하지 못할 수도 있습니다.

여기서는 이러한 탐색 알고리즘으로 너비 우선 탐색(BFS)을 사용합니다.

입력 − 그래프의 인접 행렬

출력 − 그래프가 연결되어 있습니다.

알고리즘

traverse(s, visited)

입력: 시작 노드 s와 노드의 방문 여부를 기록하는 visited 배열

출력: 시작 노드에서 도달 가능한 모든 정점을 순회합니다.

시작
   s를 방문했다고 표시한다
   s를 큐 Q에 삽입한다
   Q가 비어 있지 않은 동안 다음을 반복한다
      u ← 큐 Q에서 꺼낸 노드
      그래프의 각 노드 v에 대해 다음을 수행한다
         u와 v가 연결되어 있다면
            v를 아직 방문하지 않았다면
               v를 방문했다고 표시한다
               v를 큐 Q에 삽입한다
종료

isConnected(graph)

입력 − 그래프

출력 − 그래프가 연결되어 있으면 true, 그렇지 않으면 false

시작
   visited 배열을 선언한다
   그래프의 모든 정점 u에 대해 다음을 반복한다
      모든 노드를 미방문 상태로 초기화한다
      traverse(u, visited)를 호출한다
      아직 방문하지 않은 노드가 하나라도 남아 있다면
         false를 반환한다
   true를 반환한다
종료

예제 코드

다음은 위 알고리즘을 C++로 구현한 예제입니다.

#include<iostream>
#include<queue>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
    {0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 1, 1},
    {1, 0, 0, 0, 0},
    {0, 1, 0, 0, 0}};

void traverse(int s, bool visited[]) {
    visited[s] = true;        // s를 방문 처리
    queue<int> que;
    que.push(s);              // s를 큐에 삽입
    while(!que.empty()) {
        int u = que.front();  // 큐에서 노드를 꺼냄
        que.pop();
        for(int i = 0; i < NODE; i++) {
            if(graph[i][u]) {       // u와 i 사이에 간선이 있는 경우
                if(!visited[i]) {   // 아직 방문하지 않은 노드라면
                    visited[i] = true;
                    que.push(i);
                }
            }
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    // 모든 정점 u를 시작점으로 삼아, 모든 노드에 도달할 수 있는지 검사
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false;    // 모든 노드를 미방문 상태로 초기화
        traverse(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i])        // 방문되지 않은 노드가 있다면 연결 그래프가 아님
                return false;
        }
    }
    return true;
}

int main() {
    if(isConnected())
        cout << "그래프가 연결되어 있습니다.";
    else
        cout << "그래프가 연결되어 있지 않습니다.";
}

참고로 원본 코드의 for(int u; u < NODE; u++) 부분은 루프 변수 u가 초기화되지 않는 오류가 있으므로, 위 예제에서는 u = 0으로 초기화하도록 바로잡았습니다.

실행 결과

그래프가 연결되어 있습니다.

인접 행렬을 사용할 경우 한 번의 BFS는 O(V²)의 시간이 걸리고, 모든 정점을 시작점으로 탐색을 수행하므로 전체 시간 복잡도는 O(V³)가 됩니다. 여기서 V는 그래프의 정점 개수입니다.