フルーリーのアルゴリズムとは？オイラー路・オイラー閉路の求め方を実装例つきで解説

フルーリーのアルゴリズム（Fleury's Algorithm）とは

フルーリーのアルゴリズムは、与えられたグラフからオイラー路（Euler Path）またはオイラー閉路（Euler Circuit）を求めるための古典的なアルゴリズムです。

基本的な考え方はシンプルで、ある辺から出発し、隣接する頂点へ移動するたびに通過済みの辺を削除していきます。この操作を繰り返すことで、ステップごとにグラフが単純化され、最終的にオイラー路やオイラー閉路を効率よく発見できる仕組みになっています。

アルゴリズムを適用するための条件

オイラー路やオイラー閉路を正しく求めるためには、以下のルールを満たしている必要があります。

• 対象のグラフはオイラーグラフであること。
• 移動先の候補として「橋（ブリッジ）」となる辺と「非橋」となる辺の両方が存在する場合、必ず非橋の辺を優先して選ぶこと。

特に2番目のルールが重要です。橋となる辺を先に通ってしまうと、グラフが分断されてしまい、残りの辺をすべて辿れなくなる恐れがあるためです。

開始頂点の選び方

開始頂点の選択にも注意が必要です。任意の頂点をスタート地点にできるわけではありません。

• グラフ内に奇数次（次数が奇数）の頂点が存在しない場合：どの頂点でも開始点として選択可能です。
• 奇数次の頂点が存在する場合：その奇数次の頂点を必ず開始点として選ばなければなりません。

アルゴリズムの擬似コード

フルーリーのアルゴリズムは、主に4つの関数で構成されます。開始頂点の探索、連結性の確認（DFS）、橋の判定、そして本体となる経路構築処理です。

findStartVert(graph)
入力: 対象のグラフ
出力: アルゴリズムの開始頂点
Begin
    グラフ内の全ての頂点 i について:
        deg := 0
        i に隣接する全ての頂点 j について:
            deg := deg + 1
        もし deg が奇数なら:
            return i
    全ての次数が偶数の場合は 0 を返す
End

dfs(prev, start, visited)
入力: 直前の頂点 prev、開始頂点 start、訪問リスト visited
出力: DFS後に到達できたノード数
Begin
    count := 1
    visited[start] := true
    グラフ内の全ての頂点 u について:
        もし prev ≠ u かつ u が未訪問なら:
            もし start と u が接続していれば:
                count := count + dfs(start, u, visited)
    return count
End

isBridge(u, v)
入力: 始点 u と終点 v
出力: 辺(u, v)が橋であれば true
Begin
    deg := 0
    v に隣接する全ての頂点 i について:
        deg := deg + 1
    もし deg > 1 なら:
        return false   // 橋ではない
    return true        // 橋である
End

fleuryAlgorithm(start)
入力: 開始頂点
出力: オイラー路またはオイラー閉路の表示
Begin
    edge := グラフの辺の総数（再帰呼び出し間で保持）
    v_count := ノードの総数（再帰呼び出し間で保持）
    start に隣接する全ての頂点 v について:
        visited 配列を false で初期化
        もし isBridge(start, v) なら v_count を 1 減らす
        cnt = dfs(start, v, visited)
        もし |cnt − v_count| ≤ 2 なら:
            辺 (start → v) を表示
            もし isBridge(v, start) なら v_count を 1 減らす
            start と v の間の辺を削除
            edge を 1 減らす
            fleuryAlgorithm(v) を再帰呼び出し
End

C++による実装例

以下は、8頂点の無向グラフを隣接行列で表現し、フルーリーのアルゴリズムでオイラー路を求めるC++プログラムの例です。

#include<iostream>
#include<vector>
#include<cmath>
#define NODE 8

using namespace std;
int graph[NODE][NODE] = {
    {0,1,1,0,0,0,0,0},
    {1,0,1,1,1,0,0,0},
    {1,1,0,1,0,1,0,0},
    {0,1,1,0,0,0,0,0},
    {0,1,0,0,0,1,1,1},
    {0,0,1,0,1,0,1,1},
    {0,0,0,0,1,1,0,0},
    {0,0,0,0,1,1,0,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;    // その頂点を開始点とする
    }
    return 0; // 全て偶数次なら頂点0から開始
}

// 到達可能なノード数を数えるDFS
int dfs(int prev, int start, bool visited[]){
    int count = 1;
    visited[start] = true;
    for(int u = 0; u<NODE; u++){
        if(prev != u){
            if(!visited[u]){
                if(tempGraph[start][u]){
                    count += dfs(start, u, visited);
                }
            }
        }
    }
    return count;
}

// 辺(u, v)が橋かどうかを判定
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();
    static int v_count = NODE;
    for(int v = 0; v<NODE; v++) {
        if(tempGraph[start][v]) {
            bool visited[NODE] = {false};
            if(isBridge(start, v)){
                v_count--;
            }
            int cnt = dfs(start, v, visited);
            if(abs(v_count-cnt) <= 2){
                cout << start << "--" << v << " ";
                if(isBridge(v, start)){
                    v_count--;
                }
                tempGraph[start][v] = tempGraph[v][start] = 0; // グラフから辺を削除
                edge--;
                fleuryAlgorithm(v);
            }
        }
    }
}

int main() {
    for(int i = 0; i<NODE; i++) // 元グラフを作業用グラフへコピー
        for(int j = 0; j<NODE; j++)
            tempGraph[i][j] = graph[i][j];
    cout << "Euler Path Or Circuit: ";
    fleuryAlgorithm(findStartVert());
}

実行結果

上記のプログラムを実行すると、次のようなオイラー路が出力されます。

Euler Path Or Circuit: 0--1 1--2 2--3 3--1 1--4 4--5 5--6 6--4 4--7 7--5 5--2 2--0

この結果から、すべての辺をちょうど1回ずつ通る経路が正しく構成されていることが確認できます。フルーリーのアルゴリズムは、橋の判定とDFSによる連結チェックを組み合わせることで、常に安全な辺を選択しながらオイラー路を構築する点が大きな特徴です。