C++로 무방향 그래프의 오일러 경로 존재 여부 확인하기

오일러 경로(Eulerian Path)는 그래프의 모든 간선을 정확히 한 번씩만 통과하면서 전체 그래프를 탐색할 수 있는 경로를 말합니다. 이때 정점은 여러 번 거쳐 가더라도 문제가 되지 않습니다. 오일러 회로(Eulerian Circuit)는 오일러 경로의 한 종류로, 경로의 시작 정점과 끝 정점이 서로 연결되어 출발점으로 돌아올 수 있는 특수한 형태입니다.

무방향 그래프에 오일러 경로가 존재하는지 판별하려면 다음 조건들을 확인해야 합니다.

그래프는 반드시 연결 그래프여야 합니다.
모든 정점의 차수(degree)가 짝수라면 오일러 회로가 존재하며, 이는 곧 하나의 오일러 경로이기도 합니다.
정확히 두 개의 정점만 차수가 홀수라면 오일러 경로가 존재합니다.

입력 예시

출력 결과

두 그래프 모두 오일러 경로를 가지고 있습니다.

알고리즘

traverse(u, visited)

입력 : 시작 노드 u, 방문 여부를 표시하는 visited 배열
출력 : 시작 노드와 연결된 모든 정점을 순회합니다.

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

isConnected(graph)

입력 : 검사 대상 그래프
출력 : 그래프가 연결되어 있다면 true, 그렇지 않다면 false

visited 배열 선언
그래프의 모든 정점 u에 대하여
    모든 노드를 미방문 상태로 초기화
    traverse(u, visited)
    아직 방문하지 못한 노드가 남아 있다면
        false 반환
true 반환

isEulerian(Graph)

입력 : 주어진 그래프
출력 : 오일러 회로 또는 오일러 경로가 존재하면 1, 존재하지 않으면 0

isConnected()가 false라면
    false 반환
각 노드의 차수를 저장할 리스트 생성
oddDegree := 0
그래프의 모든 정점 i에 대하여
    i에 인접한 정점 j의 개수를 세어 차수 계산
    정점 i의 차수가 홀수라면
        oddDegree 1 증가
oddDegree가 2보다 크다면
    0 반환
그 외의 경우 1 반환

핵심 아이디어는 간단합니다. 먼저 DFS 순회를 통해 그래프가 연결되어 있는지 검사하고, 연결되어 있다면 차수가 홀수인 정점의 개수를 셉니다. 이 개수가 0이면 오일러 회로, 2이면 오일러 경로, 그 이상이면 오일러 경로가 존재하지 않습니다.

C++ 예제 코드

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 1, 1, 1, 0},
    {1, 0, 1, 0, 0},
    {1, 1, 0, 0, 0},
    {1, 0, 0, 0, 1},
    {0, 0, 0, 1, 0}};
/*int graph[NODE][NODE] = {{0, 1, 1, 1, 1},
    {1, 0, 1, 0, 0},
    {1, 1, 0, 0, 0},
    {1, 0, 0, 0, 1},
    {1, 0, 0, 1, 0}};*/ //주석을 해제하면 오일러 회로(및 경로) 여부도 함께 확인할 수 있습니다.
/*int graph[NODE][NODE] = {{0, 1, 1, 1, 0},
    {1, 0, 1, 1, 0},
    {1, 1, 0, 0, 0},
    {1, 1, 0, 0, 1},
    {0, 0, 0, 1, 0}};*/ //주석을 해제하면 오일러 경로가 없는 그래프를 확인할 수 있습니다.
void traverse(int u, bool visited[]) {
    visited[u] = true; //v를 방문 처리
    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}
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 isEulerian() {
    if(isConnected() == false) //그래프가 연결되어 있지 않은 경우
        return 0;
    vector<int> degree(NODE, 0);
    int oddDegree = 0;
    for(int i = 0; i<NODE; i++) {
        for(int j = 0; j<NODE; j++) {
            if(graph[i][j])
                degree[i]++; //연결된 간선을 찾으면 차수 증가
        }
        if(degree[i] % 2 != 0) //정점의 차수가 홀수인 경우
            oddDegree++; //차수가 홀수인 정점의 개수를 카운트
    }
    if(oddDegree > 2) //차수가 홀수인 정점이 2개보다 많은 경우
        return 0;
    return 1; //oddDegree가 0이면 오일러 회로, 2이면 오일러 경로
}
int main() {
    if(isEulerian() != 0) {
        cout << "The graph has Eulerian path." << endl;
    } else {
        cout << "The graph has No Eulerian path." << endl;
    }
}

실행 결과

The graph has Eulerian path.

위 코드는 인접 행렬 방식으로 그래프를 저장하므로, 연결성 검사와 차수 계산을 모두 고려했을 때 시간 복잡도는 O(V²)입니다. 차수가 홀수인 정점이 0개면 오일러 회로가, 정확히 2개면 오일러 경로가 존재한다는 점만 기억하면 어떤 무방향 그래프든 손쉽게 판별할 수 있습니다.