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

オイラー閉路（オイラー回路）とは、グラフ上のすべての辺をちょうど1回ずつ通過できる経路のことです。このとき、同じ頂点を何度通っても構いません。オイラー閉路はオイラー路（Euler Path）の特別な形であり、オイラー路の始点がそのまま終点ともつながっている場合を指します。

ある有向グラフがオイラー閉路を持つかどうかを判定するには、次の2つの条件を満たしている必要があります。

• グラフが連結であること（任意の頂点から他のすべての頂点へ到達できること）。

• すべての頂点において、入次数と出次数が等しいこと。

入力 − グラフの隣接行列

出力 − オイラー閉路が見つかりました（Euler Circuit Found）

アルゴリズム

traverse(u, visited)

入力 − 探索の起点となるノード u、および訪問済みノードを記録するための配列 visited。

出力 − u から到達可能なすべての頂点を探索します。

u を訪問済みとしてマークする
u に隣接するすべての頂点 v について、
   v が未訪問であれば
      traverse(v, visited) を呼び出す
終了

isConnected(graph)

入力 − 判定対象のグラフ。

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

visited 配列を用意する
グラフ内のすべての頂点 u について、
   すべてのノードを未訪問に初期化する
   traverse(u, visited) を実行する
   未訪問のノードが1つでも残っていれば
      false を返す
すべての起点から全ノードに到達できれば true を返す
終了

isEulerCircuit(Graph)

入力 − 判定対象のグラフ。

出力 − オイラー閉路が存在すれば true。

isConnected() の結果が false であれば
   false を返す
各ノードの入辺数・出辺数を格納するリストを用意する
グラフ内のすべての頂点 i について、
   sum := 0
   i につながっているすべての頂点 j について、
      頂点 i の入辺数を +1 する
      sum を +1 する
   頂点 i の出辺数として sum を記録する
入辺リストと出辺リストが一致すれば
   true を返す
そうでなければ false を返す
終了

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}};

// 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];
   // すべての頂点 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;
}

// オイラー閉路の存在を判定する
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]++;           // 行き先 j の入辺数をカウント
            sum++;                 // 頂点 i の出辺数をカウント
         }
      }
      outward[i] = sum;
   }
   // すべての頂点で入辺数と出辺数が一致していれば true
   if (inward == outward)
      return true;
   return false;
}

int main() {
   if (isEulerCircuit())
      cout << "Euler Circuit Found.";
   else
      cout << "There is no Euler Circuit.";
}

このコードでは、まず isConnected() によってグラフの連結性を確認したうえで、各頂点の入次数と出次数を比較しています。この2つの条件がそろった場合のみ、その有向グラフはオイラー閉路を持つと判定されます。

実行結果

Euler Circuit Found.

まとめ

有向グラフのオイラー閉路の判定は、「グラフが連結であること」と「すべての頂点で入次数と出次数が一致すること」という2つの条件に帰着できます。本実装のように隣接行列を用いた場合、連結性の確認のために各頂点から探索を実行するため、全体の計算量は O(V³)（Vは頂点数）となります。小規模なグラフであれば十分実用的なアプローチです。