C++로 유향 그래프의 오일러 회로(Euler Circuit) 존재 여부 확인하기

오일러 경로(Euler Path)란 그래프의 모든 간선을 정확히 한 번씩만 지나가는 경로를 의미합니다. 이때 정점(vertex)은 여러 번 반복해서 방문해도 무방합니다. 오일러 회로(Euler Circuit)는 오일러 경로의 특수한 형태로, 경로의 시작 정점과 마지막 정점이 서로 연결되어 있어 출발점으로 다시 돌아올 수 있는 경우를 말합니다.

유향 그래프(directed graph)가 오일러 회로를 가지는지 판단하려면 아래 두 가지 조건을 모두 만족해야 합니다.

• 그래프가 연결 그래프(connected graph)여야 합니다.

• 모든 정점에서 진입 차수(in-degree)와 진출 차수(out-degree)가 서로 같아야 합니다.

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

출력 − Euler Circuit Found

알고리즘

traverse(u, visited)

입력 − 시작 노드 u와 방문 여부를 표시하는 visited 배열

출력 − 시작 노드에서 도달 가능한 모든 정점을 순회

Begin
   mark u as visited
   for all vertex v, if it is adjacent with u, do
      if v is not visited, then
         traverse(v, visited)
   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

isEulerCircuit(Graph)

입력 − 주어진 그래프

출력 − 오일러 회로가 존재하면 true, 아니면 false

Begin
    if isConnected() is false, then
       return false
    define list for inward and outward edge count for each node
    for all vertex i in the graph, do
        sum := 0
        for all vertex j which are connected with i, do
           inward edges for vertex i increased
           increase sum
        done
        number of outward of vertex i is sum
    done
    if inward list and outward list are same, then
        return true
     otherwise return false
End

예제 코드(C++)

#include<iostream>
#include<vector>
#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, 0, 1, 0, 0}};
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;
}
bool isEulerCircuit() {
   if(isConnected() == false) {    // 그래프가 연결되어 있지 않은 경우
      return false;
   }
   vector<int> inward(NODE, 0), outward(NODE, 0);
   for(int i = 0; i<NODE; i++) {
      int sum = 0;
      for(int j = 0; j<NODE; j++) {
         if(graph[i][j]) {
            inward[j]++;    // 도착 정점의 진입 차수 증가
            sum++;    // 진출 간선 개수 누적
         }
      }
      outward[i] = sum;
   }
   if(inward == outward)    // 모든 정점에서 진입/진출 차수가 동일한 경우
      return true;
   return false;
}
int main() {
   if(isEulerCircuit())
      cout << "Euler Circuit Found.";
   else
      cout << "There is no Euler Circuit.";
}

실행 결과

Euler Circuit Found.

동작 원리 요약

위 프로그램은 먼저 DFS 기반의 traverse() 함수를 이용해 그래프의 연결성을 검사합니다. 모든 정점을 시작점으로 삼았을 때 나머지 정점 전체에 도달할 수 없다면 오일러 회로가 존재할 수 없습니다. 연결성 검사를 통과하면, 각 정점의 진입 차수와 진출 차수를 계산하여 두 값이 모든 정점에서 일치하는지 확인합니다. 이 조건들이 모두 충족될 때 해당 유향 그래프는 오일러 회로를 가진다고 판정할 수 있습니다. 시간 복잡도는 연결성 검사와 차수 계산 모두 인접 행렬을 순회하므로 O(V²)입니다.