Fleuryのアルゴリズム

オイラー小道をつくるアルゴリズム

[参考元] R・J・ウィルソン『グラフ理論入門』近代科学社、2013、p.45.

オイラー・グラフとは

連結グラフで、すべての辺を含む閉じた小道があるグラフをオイラーグラフと呼ぶ。
そのような小道をオイラー小道と呼ぶ。

連結グラフGがオイラーグラフであるための必要十分条件は、Gの点の次数がすべて偶数であること。

Fleuryのアルゴリズムはオイラー小道の構成法を与えるアルゴリズム。

任意の点uから出発して、次の規則に従う限り自由に辺をたどる。

1.たどった辺を除去する。もし孤立点が生じたらそれも除去する。
2.どの段階でも、他にたどる辺がない場合以外は橋をたどらない。

橋とはカットセットが１本のときの辺のこと。
直感的には、ある連結グラフから１本の辺を除いたときに非連結グラフとなるような辺。

プログラム

オイラーグラフならオイラー小道を求める。
オイラー小道は上で述べたFleuryのアルゴリズムを用いる。
橋となるかの判定は深さ優先探索でおこなう。

/* Fleuryのアルゴリズム */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_V = 20;
vector<int> G[MAX_V];
bool visited[MAX_V];
int V, E;

/* すべての頂点の次数が偶数ならばオイラーグラフ */
bool IsEulerianGraph()
{
    for (int i = 0; i < V; i++)
        if (G[i].size() % 2 != 0)
            return false;
    return true;
}

/* 橋の判定の初期化*/
void InitBridge()
{
    for (int i = 0; i < V; i++)
        visited[i] = false;
}

// 深さ優先探索で連結の確認
void dfs(int v, int s, int t)
{
    visited[v] = true;
    if (v == t)
        swap(s, t);
    for (int i = 0; i < G[v].size(); i++) {
        if (v == s && G[v][i] == t) 
            continue;

        if (!visited[G[v][i]])
            dfs(G[v][i], s, t);
    }
}

/* uvが橋であればtrue */
bool IsBridge(int u, int v)
{
    InitBridge();

    dfs(u, u, v);
    for (int i = 0; i < V; i++)
        if (!visited[i])
            return true;
    return false;
}

/* オイラー小道を返す */
vector<int> EulerCircuit()
{
    vector<int> ret;
    int e = E, v = 0;

    ret.push_back(0);
    while (e > 0) {
        bool flag = false;

        for (int i = 0; i < G[v].size(); i++) {
            if (!IsBridge(v, G[v][i])) {
                flag = true;
                int u = G[v][i];
                G[v].erase(G[v].begin() + i);
                for (int j = 0; j < G[u].size(); j++)
                    if (G[u][j] == v)
                        G[u].erase(G[u].begin() + j);
                v = u;
                e--;
                break;
            }
        }

        if (!flag) {

            int u = G[v][0];
            G[v].erase(G[v].begin());
            for (int i = 0; i < G[u].size(); i++)
                if (G[u][i] == v)
                    G[u].erase(G[u].begin() + i);
            v = u;
            e--;
        }

        ret.push_back(v);
    }
    
    return ret;
}


int main()
{
    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        int s, t;
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    if (!IsEulerianGraph())
        cout << "オイラーグラフではありません" << endl;
    else {
        vector<int> trail = EulerCircuit();

        for (int i = 0; i < trail.size(); i++)
            cout << trail[i] << " ";
        cout << endl;
    }

    return 0;
}

TODO
簡単な場合のverifiedしかしていない。
橋の判定をもっとスマートに
入力のグラフを変形しているので修正