重みなしグラフでハミルトン閉路を検出するC++プログラムの実装方法

ハミルトン閉路とは？

ハミルトン閉路（Hamiltonian Cycle）とは、グラフ上のすべての頂点をちょうど一度ずつ通過する閉じた経路のことです。ハミルトン路の終点から始点へ戻る辺がグラフ内に存在するとき、その経路はハミルトン閉路と呼ばれます。本記事では、重み付けのない無向グラフを対象に、バックトラッキング法を用いてハミルトン閉路を検出するC++プログラムを紹介します。

使用する関数とその役割

このプログラムは、次の3つの関数で構成されています。

• isSafe()：追加候補の頂点が「直前に追加した頂点と隣接しているか」「すでに経路に含まれていないか」をチェックします。
• hamiltonianCycle()：再帰とバックトラッキングによってハミルトン閉路問題そのものを解きます。
• hamCycle()：hamiltonianCycle()を呼び出して問題を解決します。ハミルトン閉路が存在しなければfalseを返し、存在すればtrueを返して経路を表示します。

C++による実装例

以下は、隣接行列で表現した5頂点のグラフに対してハミルトン閉路を探索するサンプルコードです。g[i][j]が1のとき、頂点iと頂点jの間に辺が存在することを表します。

#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<<"\n閉路は存在しません"<<endl;
        return false;
    }
    displaytheSolution(path);
    return true;
}
void displaytheSolution(int p[]) {
    cout<<"閉路が存在します:";
    cout<<" 以下はハミルトン閉路の一例です \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;
}

実行結果

閉路が存在します: 以下はハミルトン閉路の一例です
0 4 1 2 3 0

アルゴリズムのポイント

このプログラムはバックトラッキングによって動作します。頂点0を起点として経路を1つずつ伸ばしていき、条件を満たさなくなった時点で直前の選択を取り消して別の頂点を試します。すべての頂点を訪れたうえで、最後の頂点から起点へ戻る辺が存在すれば、ハミルトン閉路が見つかったことになります。

なお、ハミルトン閉路の判定はNP完全問題であり、この手法の最悪計算量はO(N!)オーダーになります。頂点数が大きくなると実行時間が急激に増大するため、実用的には小規模なグラフに適した手法である点に留意してください。