【C++】無向グラフにオイラー路が存在するかどうかを判定する方法

オイラー路（Euler Path）とは、グラフ上のすべての辺をちょうど1回ずつ通る経路のことです。途中で同じ頂点を何度訪れることは許されますが、同じ辺を2回以上使うことはできません。

また、オイラー閉路（Euler Circuit）はオイラー路の特殊なケースで、経路の始点と終点が同じ頂点でつながっているものを指します。

オイラー路が存在するための条件

無向グラフにオイラー路が存在するかどうかは、次の条件で判定できます。

• グラフが連結であること
• 奇数次数の頂点が0個の場合：オイラー閉路が存在します。オイラー閉路はオイラー路の一種でもあります。
• 奇数次数の頂点がちょうど2個の場合：オイラー路が存在します。このとき、奇数次数の2つの頂点がそれぞれ始点と終点になります。
• 奇数次数の頂点が3個以上の場合：オイラー路は存在しません。

入力と出力

入力：隣接行列で表された無向グラフ
出力：そのグラフがオイラー路を持つかどうかの判定結果

下図の2つのグラフは、どちらもオイラー路を持っています。

アルゴリズム

traverse(u, visited)

入力：探索の起点となる頂点 u と、訪問済みノードを記録する visited 配列

出力：u から到達可能なすべての頂点を訪問する

手順：
1. 頂点 u を訪問済みとしてマークする
2. u に隣接するすべての頂点 v について、次を行う
     v が未訪問であれば、traverse(v, visited) を再帰的に呼び出す

isConnected(graph)

入力：判定対象のグラフ

出力：グラフが連結であれば true、そうでなければ false

手順：
1. visited 配列を用意する
2. グラフ内の各頂点 u を起点として、次を行う
     すべてのノードを未訪問状態に初期化する
     traverse(u, visited) を実行する
     未訪問のノードが残っている場合は false を返す
3. すべての頂点を起点にしても未訪問ノードが現れなければ true を返す

isEulerian(Graph)

入力：与えられたグラフ

出力：オイラー閉路またはオイラー路が存在すれば 1、存在しなければ 0 を返す

手順：
1. isConnected() が false であれば 0 を返す
2. 各ノードの次数を格納するリストを用意する
3. oddDegree := 0 と初期化する
4. グラフ内の各頂点 i について、次を行う
     i に接続されている各頂点 j に対して degree[i] を 1 増やす
     頂点 i の次数が奇数であれば oddDegree を 1 増やす
5. oddDegree が 2 より大きければ 0 を返す
6. それ以外は 1 を返す（oddDegree が 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}}; */

// 深さ優先探索で、u から到達可能な頂点をすべて訪問する
void traverse(int u, bool visited[]) {
    visited[u] = true; // u を訪問済みとしてマーク
    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 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²) となります。頂点数 V に対して辺の数 E が少ないスパースなグラフでは、隣接リストを採用することで O(V + E) まで効率化できます。