BFS(너비 우선 탐색)로 무방향 그래프의 연결성을 확인하는 C++ 프로그램

그래프 연결성 확인의 기본 개념

그래프가 연결되어 있는지 확인하려면 임의의 순회(traversal) 알고리즘을 사용해 모든 노드를 방문해 봅니다. 순회가 완료된 후에도 방문하지 않은 노드가 하나라도 남아 있다면, 해당 그래프는 연결되어 있지 않다고 판단할 수 있습니다.

무방향 그래프(undirected graph)의 경우에는 아무 노드나 하나 선택한 뒤, 그 노드에서부터 탐색을 시작합니다. 이 글에서는 큐(queue)를 활용한 너비 우선 탐색(BFS, Breadth-First Search)으로 연결성을 검사하는 방법을 다룹니다.

입력 − 그래프의 인접 행렬(adjacency matrix)

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

알고리즘

traverse(s, visited)

입력 − 시작 노드 s와 각 노드의 방문 여부를 기록할 visited 배열

출력 − 시작 노드와 연결된 모든 정점을 순회

Begin
   mark s as visited
   insert s into a queue Q
   until the Q is not empty, do
   u = node that is taken out from the queue
   for each node v of the graph, do
      if the u and v are connected, then
         if v is not visited, then
            mark v as visited
            insert v into the queue Q.
      done
   done
End

isConnected(graph)

입력 − 그래프

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

Begin
   define visited array
   for all vertices u in the graph, do
      make all nodes unvisited
      traverse(u, visited)
      if any unvisited node is still remaining, then
         return false
   done
   return true
End

C++ 예제 코드

#include<iostream>
#include<queue>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
   {0, 1, 1, 0, 0},
   {1, 0, 1, 1, 0},
   {1, 1, 0, 1, 1},
   {0, 1, 1, 0, 1},
   {0, 0, 1, 1, 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]) {
            //아직 방문하지 않은 노드인 경우
            if(!visited[i]) {
               visited[i] = true;
               que.push(i);
            }
         }
      }
   }
}
bool isConnected() {
   bool *vis = new bool[NODE];
   //모든 정점을 시작점으로 삼아 모든 노드에 도달 가능한지 검사
   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 << "The Graph is connected.";
   else
      cout << "The Graph is not connected.";
}

실행 결과

The Graph is connected.

동작 원리 정리

이 프로그램의 핵심 로직은 다음과 같습니다.

• BFS 순회(traverse): 시작 노드를 큐에 넣고, 큐가 빌 때까지 앞에서 노드를 하나씩 꺼내며 인접한 미방문 노드를 모두 큐에 추가합니다.
• 연결성 검사(isConnected): 각 정점을 시작점으로 삼아 BFS를 수행한 뒤, 모든 노드가 방문되었는지 확인합니다. 방문되지 않은 노드가 하나라도 있으면 즉시 false를 반환합니다.
• 시간 복잡도: 인접 행렬을 사용하므로 한 번의 BFS는 O(V²)이며, 모든 정점을 시작점으로 검사하는 이 구현은 최악의 경우 O(V³)입니다.

참고로 무방향 그래프에서는 어느 한 정점에서 시작한 단 한 번의 BFS만으로도 연결성 여부를 판별할 수 있습니다. 시작 정점에서 도달한 노드 수가 전체 정점 수와 같다면 연결 그래프입니다. 위 코드처럼 모든 정점을 시작점으로 반복 검사하는 방식은 안전성을 높이는 접근이지만, 실제로는 한 번의 순회로 충분합니다.