Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

DFS를 활용해 무방향 그래프의 연결성을 확인하는 C++ 프로그램

그래프의 연결성(connectivity)을 확인하려면 임의의 그래프 순회(traversal) 알고리즘을 사용해 모든 노드를 방문해 보면 됩니다. 순회가 끝난 뒤에도 방문되지 않은 노드가 하나라도 남아 있다면, 해당 그래프는 연결되어 있지 않은 것입니다.

기본 아이디어

무방향 그래프(undirected graph)에서는 먼저 하나의 정점을 선택한 후, 그 정점에서부터 탐색을 시작합니다.

여기서 사용하는 순회 알고리즘은 재귀적 DFS(깊이 우선 탐색)입니다.

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

01100
10110
11011
01101
00110

출력 − The Graph is connected. (그래프는 연결되어 있습니다.)

알고리즘

traverse(u, visited)

입력 − 시작 정점 u와, 방문한 노드를 표시하기 위한 visited 배열

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

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

isConnected(graph)

입력 − 그래프

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

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

C++ 예제 코드

#include<iostream>
#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}};

// u와 연결된 모든 정점을 재귀적으로 방문
void traverse(int u, bool visited[]) {
   visited[u] = true; // 현재 정점을 방문 처리
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]) {
         if(!visited[v])
            traverse(v, visited);
      }
   }
}

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.

동작 원리 정리

  1. 각 정점을 차례대로 시작점으로 지정하고 DFS를 수행합니다.
  2. DFS가 종료되면 visited 배열을 검사해 방문되지 않은 정점이 있는지 확인합니다.
  3. 방문되지 않은 정점이 하나라도 있으면 그래프는 연결되어 있지 않으므로 false를 반환합니다.
  4. 모든 시작점에 대해 위 검사를 통과하면 그래프는 연결되어 있는 것이므로 true를 반환합니다.

시간 복잡도

인접 행렬을 사용할 때 한 번의 DFS 순회에는 O(V²)의 시간이 소요됩니다. 이를 V개의 시작 정점마다 반복하므로 전체 시간 복잡도는 O(V³)입니다.

참고: 무방향 그래프의 연결성은 사실 임의의 한 정점에서 단 한 번의 DFS만 수행해도 판별할 수 있습니다. 한 번의 순회로 모든 정점이 방문된다면 그 그래프는 연결된 그래프이기 때문입니다. 따라서 실무에서는 시작 정점 하나만 골라 순회하는 방식이 더 효율적입니다.