無向グラフにオイラー閉路が含まれるかどうかを判定するC++プログラム

オイラー閉路（Euler Circuit）について学ぶには、まずオイラー路（Euler Path）という概念を理解しておく必要があります。オイラー路とは、グラフ内のすべての辺をちょうど一度ずつ通過できる経路のことであり、同じ頂点を複数回通ることは許されます。

オイラー閉路は、オイラー路の特別なケースです。オイラー路の始点となる頂点が、そのまま終点の頂点にも接続されており、経路が一つの閉じた周回路となっているものを指します。

オイラー閉路の判定条件

無向グラフがオイラー閉路を持つかどうかを調べるには、次の2つの条件を確認します。

• グラフが連結であること ── すべての頂点が辺を介して互いに到達可能である必要があります。
• すべての頂点の次数が偶数であること ── 無向グラフの全頂点が奇数の次数を持たない場合、そのグラフはオイラー閉路を持ちます。

入力例

以下のような隣接行列で表現された無向グラフを入力として考えます。

graph[5][5] = {
  {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}
};

出力

このグラフはオイラー閉路を持ちます。

アルゴリズム

traverse(u, visited)

入力：開始ノード u、および訪問済みノードを記録する visited 配列

出力：u から到達できるすべての連結頂点を探索します。

開始
    u を訪問済みとしてマーク
    u に隣接するすべての頂点 v に対して、次を実行
        v が未訪問ならば
            traverse(v, visited) を呼び出す
終了

isConnected(graph)

入力：グラフ

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

開始
    visited 配列を定義
    グラフ内のすべての頂点 u に対して、次を実行
        すべてのノードを未訪問に戻す
        traverse(u, visited) を呼び出す
        未訪問のノードが残っていれば
            false を返す
    true を返す
終了

hasEulerianCircuit(Graph)

入力：与えられたグラフ

出力：オイラー閉路が存在しない場合は 0、存在する場合は 1 を返します。

開始
    isConnected() の結果が false の場合は
        false（0）を返す
    各ノードの次数リストを定義
    oddDegree := 0
    グラフ内のすべての頂点 i に対して、次を実行
        i に接続されているすべての頂点 j に対して
            次数を 1 増やす
        頂点 i の次数が奇数であれば
            oddDegree を 1 増やす
    oddDegree が 0 であれば
        1 を返す
    それ以外は 0 を返す
終了

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; //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];
    //すべての頂点 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 hasEulerianCircuit() {
    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 == 0) { //oddDegree が 0 ならオイラー閉路
        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.

計算量について

この実装では、連結性の判定のために各頂点を起点とした深さ優先探索を行い、さらに全頂点間の接続を走査して次数を集計しています。隣接行列を使用しているため、頂点数を V とすると全体の計算量は O(V³) 程度になります。頂点数や辺の数が多い大規模なグラフを扱う場合は、隣接リスト表現を用いることで効率を大幅に改善できます。