DFS(깊이 우선 탐색)로 방향 그래프의 연결성을 확인하는 C++ 프로그램

그래프의 연결성을 확인하려면 임의의 그래프 순회 알고리즘을 이용해 모든 노드를 방문할 수 있는지 검사해야 합니다. 순회가 완료된 후에도 한 번도 방문되지 않은 노드가 남아 있다면, 그 그래프는 연결되어 있지 않은 것으로 판단합니다.

방향 그래프(directed graph)의 경우에는 상황이 조금 더 복잡합니다. 어떤 간선은 바깥쪽으로만 향하고 안쪽으로 들어오는 간선이 없을 수 있기 때문에, 다른 노드를 시작점으로 삼으면 도달할 수 없는 노드가 발생할 수 있습니다. 따라서 방향 그래프의 연결성을 제대로 확인하려면 모든 노드를 시작점으로 삼아 순회를 수행해야 합니다.

이 글에서는 재귀 방식의 DFS(깊이 우선 탐색)를 순회 알고리즘으로 사용합니다.

입력 및 출력

입력: 그래프의 인접 행렬

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

알고리즘

traverse(u, visited)

입력: 시작 노드 u, 방문 여부를 기록하는 visited 배열

출력: u와 연결된 모든 정점을 순회

시작
   u를 방문한 것으로 표시한다.
   u와 인접한 모든 정점 v에 대하여 다음을 반복한다.
      v를 아직 방문하지 않았다면
         traverse(v, visited)를 호출한다.
   반복 종료
끝

isConnected(graph)

입력: 검사 대상 그래프

출력: 그래프가 연결되어 있으면 true, 아니면 false

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

예제 코드

#include<iostream>
#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 u, bool visited[]) {
    visited[u] = true;      // 현재 노드 u를 방문 처리
    for(int v = 0; v<NODE; v++) {
       if(graph[u][v]) {      // u에서 v로 가는 간선이 존재하면
          if(!visited[v])    // v를 아직 방문하지 않았다면
             traverse(v, visited);    // 재귀적으로 DFS 수행
       }
   }
}

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 << "그래프는 연결되어 있지 않습니다.";
}

실행 결과

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

위 코드는 각 정점을 시작점으로 DFS를 한 번씩 수행한 뒤, 모든 정점이 방문되었는지 확인하는 방식으로 동작합니다. 정점 수를 V, 간선 수를 E라고 할 때 시간 복잡도는 O(V × (V + E))가 되며, 정점마다 전체 DFS를 반복 수행하기 때문입니다. 작은 규모의 그래프에서는 충분히 실용적인 연결성 검사 방법입니다.