C++でグラフにハミルトン閉路が存在するかどうかを判定するプログラム

ハミルトン閉路（Hamiltonian Cycle）とは、グラフ内のすべての頂点をちょうど1回ずつ訪れる閉じた経路のことです。具体的には、ハミルトン経路（Hamiltonian Path）の最後の頂点から最初の頂点へ戻る辺がグラフ中に存在するとき、その経路はハミルトン閉路と呼ばれます。本記事では、無向グラフに対してハミルトン閉路が存在するかどうかをバックトラッキング法で判定するC++プログラムを紹介します。

使用する関数とその役割

Begin
    1. isSafe()関数：追加しようとしている頂点が、直前に追加した頂点と隣接しているか、
       まだ経路に含まれていないかを確認します。
    2. hamiltonianCycle()関数：ハミルトン閉路問題を再帰的に解きます。
    3. hamCycle()関数：hamiltonianCycle()を呼び出して問題全体を解決します。
       ハミルトン閉路が存在しない場合はfalseを返し、
       存在する場合はtrueを返して経路を出力します。
End

C++サンプルコード

以下の例では、5つの頂点を持つ無向グラフを隣接行列で表現し、ハミルトン閉路の有無を判定しています。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 5
using namespace std;
void displaytheSolution(int path[]);
bool isSafe(int n, bool g[N][N], int path[], int pos) {
    if (g [path[pos-1]][n] == 0)
        return false;
    for (int i = 0; i < pos; i++)
        if (path[i] == n)
            return false;
    return true;
}
bool hamiltonianCycle(bool g[N][N], int path[], int pos) {
    //すべての頂点がハミルトン閉路に含まれたかを判定
    if (pos == N) {
        if (g[ path[pos-1] ][ path[0] ] == 1)
            return true;
        else
            return false;
    }
    for (int n = 1; n < N; n++) {
        if (isSafe(n, g, path, pos)) //この頂点を経路に追加できるかチェック
        {
            path[pos] = n;
            //残りの経路を再帰的に構築
            if (hamiltonianCycle (g, path, pos+1) == true)
                return true;
            path[pos] = -1; //解に至らない場合は頂点を取り除く（バックトラッキング）
        }
    }
    return false;
}
bool hamCycle(bool g[N][N]) {
    int *path = new int[N];
    for (int i = 0; i < N; i++)
        path[i] = -1;
    //頂点0を経路の起点とする。
    //グラフが無向であれば、閉路は任意の頂点から開始できるため
    path[0] = 0;
    if (hamiltonianCycle(g, path, 1) == false) {
        cout<<"\nCycle does not exist"<<endl;
        return false;
    }
    displaytheSolution(path);
    return true;
}
void displaytheSolution(int p[]) {
    cout<<"Cycle Exists:";
    cout<<" Following is one Hamiltonian Cycle \n"<<endl;
    for (int i = 0; i < N; i++)
        cout<<p[i]<<" ";
        cout<< p[0]<<endl;
}
int main() {
    bool g[N][N] = {
        {0, 1, 0, 1, 1},
        {0, 0, 1, 1, 0},
        {0, 1, 0, 1, 1},
        {1, 1, 1, 0, 1},
        {0, 1, 1, 0, 0},
    };
    hamCycle(g);
    return 0;
}

実行結果

Cycle Exists: Following is one Hamiltonian Cycle
0 4 1 2 3 0

アルゴリズムのポイント

このプログラムはバックトラッキング（探索の巻き戻し）を用いています。頂点を順番に経路へ追加していき、条件を満たさなくなった時点で直前の選択を取り消し、別の候補を試します。

なお、ハミルトン閉路問題はNP完全問題として知られており、この手法の最悪計算量はO(N!)になります。そのため、頂点数が多いグラフを扱う場合は、ビットDP（動的計画法）によるO(2^N × N^2)の手法など、より効率的なアプローチを検討するとよいでしょう。