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

오일러 회로(Euler Circuit)를 이해하려면 먼저 오일러 경로(Euler Path)의 개념을 알아야 합니다. 오일러 경로란 그래프의 모든 정점을 정확히 한 번씩 방문할 수 있는 경로를 의미합니다. 단, 간선은 여러 번 사용할 수 있습니다. 오일러 회로는 오일러 경로의 특수한 형태로, 경로의 시작 정점과 끝 정점이 서로 연결되어 있는 경우를 말합니다.

그래프에 오일러 회로가 존재하는지 판별하려면 다음 두 가지 조건을 만족해야 합니다.

• 그래프는 반드시 연결 그래프(Connected Graph)여야 합니다.
• 무방향 그래프에서 모든 정점의 차수(degree)가 짝수라면 해당 그래프는 오일러 회로를 가집니다.

입력 예시

5개의 정점으로 구성된 무방향 그래프를 인접 행렬 형태로 입력받습니다.

출력 결과

The graph has Euler Circuit.

알고리즘

1. traverse(u, visited)

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

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

2. 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

3. hasEulerianCircuit(Graph)

입력: 주어진 그래프
출력: 오일러 회로가 없으면 0, 존재하면 1을 반환합니다.

Begin
    if isConnected() is false, then
    return false
    define list of degree for each node
    oddDegree := 0
    for all vertex i in the graph, do
        for all vertex j which are connected with i, do
            increase degree
        done
        if degree of vertex i is odd, then
            increase oddDegree
        done
        if oddDegree is 0, then
            return 1
    else return 0
End

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}};*/ //No Euler circuit, but euler path is present
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}}; //uncomment to check Euler Circuit as well as path
/*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}};*/ //Uncomment to check Non Eulerian Graph
void traverse(int u, bool visited[]) {
    visited[u] = true; //mark v as visited
    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 all vertex u as start point, check whether all nodes are visible or not
    for(int u; u < NODE; u++) {
        for(int i = 0; i<NODE; i++)
            vis[i] = false; //initialize as no node is visited
            traverse(u, vis);
            for(int i = 0; i<NODE; i++) {
                if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected
                return false;
            }
    }
    return true;
}
int hasEulerianCircuit() {
    if(isConnected() == false) //when graph is not connected
    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]++; //increase degree, when connected edge found
        }
        if(degree[i] % 2 != 0) //when degree of vertices are odd
        oddDegree++; //count odd degree vertices
    }
    if(oddDegree == 0) { //when oddDegree is 0, it is Euler circuit
        return 1;
    }
    return 0;
}
int main() {
    if(hasEulerianCircuit()) {
        cout << "The graph has Eulerian Circuit." << endl;
    } else {
        cout << "The graph has No Eulerian Circuit." << endl;
    }
}

실행 결과

The graph has Eulerian Circuit.