有向グラフにオイラー路が存在するか判定するC++プログラム

オイラー路とは

オイラー路（Euler Path）とは、グラフのすべての辺をちょうど1回ずつ通ることのできる経路のことです。途中で同じ頂点を何度訪れても問題ありません。なお、オイラー閉路（Euler Circuit）を含むグラフも、始点と終点が一致するオイラー路を持つとみなされるため、本記事では両方を扱います。

有向グラフがオイラー路を持つための条件

有向グラフにオイラー路が存在するかどうかを判定するには、次の3つの条件を確認する必要があります。

• 出次数 ＝ 入次数 ＋ 1 となる頂点がちょうど1つ存在すること
• 入次数 ＝ 出次数 ＋ 1 となる頂点がちょうど1つ存在すること
• 残りのすべての頂点において、入次数 ＝ 出次数 が成り立つこと

これらの条件のいずれかが満たされない場合、そのグラフにはオイラー路は存在しません。さらに、グラフが連結であることも大前提となります。

上図の例では、頂点bが「入次数1・出次数2」、頂点cが「入次数2・出次数1」となり、残りの頂点a・dは「入次数2・出次数2」、頂点eは「入次数1・出次数1」です。つまり、条件に該当する頂点がそれぞれ1つずつ存在するため、このグラフにはオイラー路が存在します。

入力

グラフの隣接行列。

出力

オイラー路が見つかりました（Euler Path Found）。

アルゴリズム

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

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

hasEulerPath(Graph)

入力：対象となるグラフ
出力：オイラー路が存在すればtrue、存在しなければfalse

Begin
    an := 0
    bn := 0
    if isConnected() is false, then
        return false
    define list for inward and outward edge count for each node
    for all vertex i in the graph, do
        sum := 0
        for all vertex j which are connected with i, do
            inward edges for vertex i increased
            increase sum
        done
        number of outward of vertex i is sum
    done
    if inward list and outward list are same, then
        return true
    for all vertex i in the vertex set V, do
        if inward[i] ≠ outward[i], then
            if inward[i] + 1 = outward[i], then
                an := an + 1
            else if inward[i] = outward[i] + 1, then
                bn := bn + 1
    done
    if an and bn both are 1, then
        return true
    otherwise return false
End

処理の流れとしては、まず深さ優先探索（DFS）によってグラフの連結性を確認し、その後、各頂点の入次数と出次数を数えて上記の条件と照合します。隣接行列を使用した場合、計算量はO(V²)になります。

サンプルコード（C++）

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 0, 1, 1, 0},
    {1, 0, 1, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 1},
    {1, 0, 0, 0, 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;
}
bool hasEulerPath() {
    int an = 0, bn = 0;
    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]++; // 行き先頂点の入次数をカウント
                sum++; // 出方向の辺の数
            }
        }
        outward[i] = sum;
    }
    // オイラー路の条件をチェック
    if(inward == outward) // 全ノードで入次数と出次数が一致する場合
        return true; // オイラー閉路 → オイラー路も存在
    for(int i = 0; i<NODE; i++) {
        if(inward[i] != outward[i]) {
            if((inward[i] + 1 == outward[i])) {
                an++;
            } else if((inward[i] == outward[i] + 1)) {
                bn++;
            }
        }
    }
    if(an == 1 && bn == 1) { // anとbnがそれぞれ1つだけならオイラー路あり
        return true;
    }
    return false;
}
int main() {
    if(hasEulerPath())
        cout << "Euler Path Found.";
    else
        cout << "There is no Euler Path.";
}

実行結果

Euler Path Found.