C++でオイラー路・オイラー閉路を出力するFleuryのアルゴリズム

Fleuryのアルゴリズムとは

Fleury（フルーリー）のアルゴリズムは、与えられたグラフからオイラー路またはオイラー閉路を求めて表示するための古典的なアルゴリズムです。ある辺から出発し、通過した辺を削除しながら隣接する頂点へ移動していくことで、各ステップでグラフを単純化し、オイラー路・オイラー閉路を見つけやすくします。

オイラー路・オイラー閉路を求めるためのルール

経路や閉路を正しく求めるには、あらかじめ次のルールを確認しておく必要があります。

• グラフはオイラーグラフ（連結グラフであり、奇数次の頂点が0個または2個）であること。
• 候補となる辺が2つあり、一方が橋（ブリッジ）、もう一方が非橋である場合は、必ず非橋の辺を先に選択すること。

始点の選び方

始点の選択も重要なポイントです。どの頂点でも始点にできるわけではありません。

• グラフに奇数次の頂点が存在しない場合：任意の頂点を始点として選べます。
• 奇数次の頂点が存在する場合：その頂点を必ず始点として選ぶ必要があります。

入力

グラフの隣接行列：

出力

オイラー路またはオイラー閉路：1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2

アルゴリズム

findStartVert(graph)
入力：与えられたグラフ
出力：アルゴリズムの開始頂点を見つける
Begin
　　グラフ内のすべての頂点 i について
　　　　deg := 0
　　　　i に隣接するすべての頂点 j について
　　　　　　deg := deg + 1
　　　　繰り返し終了
　　　　もし deg が奇数なら
　　　　　　return i
　　　　終了
　　すべての次数が偶数の場合は 0 を返す
End

isBridge(u, v)
入力：始点ノードと終点ノード
出力：u と v が橋を形成する場合 true
Begin
　　deg := 0
　　v に隣接するすべての頂点 i について
　　　　deg := deg + 1
　　繰り返し終了
　　もし deg > 1 なら
　　　　return false
　　return true
End

fleuryAlgorithm(start)
入力：開始頂点
出力：オイラー路またはオイラー閉路を表示
Begin
　　edge := グラフ内の辺の本数を取得 // 次の再帰呼び出しでは初期化されない
　　start に隣接するすべての頂点 v について
　　　　もし edge <= 1 または isBridge(start, v) が false なら
　　　　　　start から v への経路を表示
　　　　　　グラフから辺 (start, v) を削除
　　　　　　edge を 1 減らす
　　　　　　fleuryAlgorithm(v)
　　繰り返し終了
End

C++による実装例

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 1, 1, 1, 1},
    {1, 0, 1, 1, 0},
    {1, 1, 0, 1, 0},
    {1, 1, 1, 0, 1},
    {1, 0, 0, 1, 0}
};
int tempGraph[NODE][NODE];
int findStartVert(){
    for(int i = 0; i<NODE; i++){
        int deg = 0;
        for(int j = 0; j<NODE; j++){
            if(tempGraph[i][j])
            deg++; // 接続する辺が見つかったら次数を増やす
        }
        if(deg % 2 != 0) // 頂点の次数が奇数の場合
        return i; // i は奇数次の頂点
    }
    return 0; // すべての頂点の次数が偶数の場合は 0 から開始
}
bool isBridge(int u, int v){
    int deg = 0;
    for(int i = 0; i<NODE; i++)
        if(tempGraph[v][i])
            deg++;
        if(deg>1){
            return false; // この辺は橋を形成していない
        }
    return true; // 辺が橋を形成している
}
int edgeCount(){
    int count = 0;
    for(int i = 0; i<NODE; i++)
        for(int j = i; j<NODE; j++)
            if(tempGraph[i][j])
                count++;
    return count; // グラフ内の辺の本数を数える
}
void fleuryAlgorithm(int start){
    static int edge = edgeCount();
    for(int v = 0; v<NODE; v++){
        if(tempGraph[start][v]){ // 辺 (u,v) が存在し、橋を形成していない場合
            if(edge <= 1 || !isBridge(start, v)){
                cout << start << "--" << v << " ";
                tempGraph[start][v] = tempGraph[v][start] = 0; // グラフから辺を削除
                edge--; // 辺の数を減らす
                fleuryAlgorithm(v);
            }
        }
    }
}
int main(){
    for(int i = 0; i<NODE; i++) // 元のグラフを tempGraph にコピー
    for(int j = 0; j<NODE; j++)
    tempGraph[i][j] = graph[i][j];
    cout << "Euler Path Or Circuit: ";
    fleuryAlgorithm(findStartVert());
}

実行結果

Euler Path Or Circuit: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2

計算量について

Fleuryのアルゴリズムでは、各ステップで「その辺が橋かどうか」の判定を行うため、辺数を E、頂点数を V とすると、全体の計算量は O(E·(V+E)) 程度になります。より高速な Hierholzer のアルゴリズム（O(V+E)）も知られていますが、Fleuryのアルゴリズムは「橋を最後に残す」という発想が直感的で、仕組みを理解しやすいのが大きな特徴です。