ハミルトン閉路とは？定義とバックトラッキングによる探索アルゴリズムを解説

ハミルトン閉路（Hamiltonian Cycle）は、グラフ理論における重要な概念の一つです。無向グラフにおいて、すべての頂点をちょうど一度ずつ訪れる経路を「ハミルトン経路（Hamiltonian Path）」と呼びます。さらに、その経路の最後の頂点から最初の頂点へ戻る辺が存在する場合、この経路を「ハミルトン閉路（ハミルトンサイクル）」または「ハミルトン回路」と呼びます。

本記事では、与えられたグラフがハミルトン閉路を持つかどうかを判定する問題を扱い、閉路が存在する場合にはその閉路そのものを出力するアルゴリズムを解説します。なお、この種の問題はNP完全であることが知られており、一般的にはバックトラッキング（探索の枝刈り）を用いた手法が採用されます。

入力と出力

入力：
グラフ G(V, E) の隣接行列

出力：
アルゴリズムは与えられたグラフのハミルトン閉路を検出します。
この例では (0, 1, 2, 4, 3, 0) が見つかります。
なお、一つのグラフに複数のハミルトン閉路が存在することもあります。
ハミルトン閉路が存在しない場合は、false を返します。

アルゴリズム

このアルゴリズムは、頂点を一つずつ経路に追加しながら、条件を満たさなくなった時点で直前の選択を取り消して別の候補を試す「バックトラッキング法」に基づいています。処理は次の二つの関数で構成されます。

isValid(v, k)

入力： 頂点 v と位置 k
出力： 頂点 v を位置 k に配置できるかどうかを判定します。

Begin
    if 頂点 node(k-1) から v への辺が存在しない場合
        return false
    if v がすでに経路に含まれている場合
        return false
    return true; // 上記以外の場合は配置可能
End

cycleFound(node k)

入力： グラフのノード
出力： ハミルトン閉路が存在すれば true、存在しなければ false を返します。

Begin
    if すべてのノードが経路に含まれている場合
        if ノード k とノード 0 の間に辺が存在する場合
            return true
        else
            return false;

    for 始点以外のすべての頂点 v について繰り返す
        if isValid(v, k) が真の場合 // v を追加できるとき
            経路に v を追加する
            if cycleFound(k+1) が true の場合
                return true
            そうでなければ、経路から v を取り除く（バックトラック）
    done
    return false
End

ポイントは、再帰呼び出し cycleFound(k+1) が失敗した際に、追加した頂点を経路から削除して別の頂点を試す点です。これにより、行き詰まった探索経路を効率的に放棄できます。

C++による実装例

#include<iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 0, 1, 0},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 0, 1},
    {1, 1, 0, 0, 1},
    {0, 1, 1, 1, 0},
};
    
/* ハミルトン閉路が存在しないグラフの例
int graph[NODE][NODE] = {
    {0, 1, 0, 1, 0},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 0, 1},
    {1, 1, 0, 0, 0},
    {0, 1, 1, 0, 0},
}; */

int path[NODE];

void displayCycle() {
    cout<<"Cycle: ";

    for (int i = 0; i < NODE; i++)
        cout << path[i] << " ";
    cout << path[0] << endl;      // 始点を再度表示して閉路を表す
}

bool isValid(int v, int k) {
    if (graph [path[k-1]][v] == 0)   // 辺が存在しない場合
        return false;

    for (int i = 0; i < k; i++)   // すでに使用済みの頂点は除外
        if (path[i] == v)
            return false;
    return true;
}

bool cycleFound(int k) {
    if (k == NODE) {          // すべての頂点が経路に含まれた場合
        if (graph[path[k-1]][ path[0] ] == 1 )
            return true;
        else
            return false;
    }

    for (int v = 1; v < NODE; v++) {       // 始点以外のすべての頂点を試す
        if (isValid(v,k)) {                // v を経路に追加できる場合
            path[k] = v;
            if (cycleFound (k+1) == true)
                return true;
            path[k] = -1;                  // 解に含めない場合は元に戻す
        }
    }
    return false;
}

bool hamiltonianCycle() {
    for (int i = 0; i < NODE; i++)
        path[i] = -1;
    path[0] = 0; // 始点を頂点 0 に固定

    if ( cycleFound(1) == false ) {
        cout << "Solution does not exist"<<endl;
        return false;
    }

    displayCycle();
    return true;
}

int main() {
    hamiltonianCycle();
}

実行結果

Cycle: 0 1 2 4 3 0

この実装では、始点を頂点 0 に固定しているため、探索の組み合わせ数を大幅に削減できます（閉路は回転しても同一とみなせるため）。最悪計算量は O(N!) となり、頂点数が増えると爆発的に増加しますが、小規模なグラフであれば十分に実用的なアプローチです。