与えられたグラフにハミルトン閉路が存在するかどうかをチェックするC++プログラム

ハミルトン閉路（Hamiltonian Cycle）とは、ハミルトン経路の一種であり、経路の最後の頂点から最初の頂点へ戻る辺がグラフ内に存在するものを指します。無向グラフにおけるハミルトン閉路とは、グラフのすべての頂点をちょうど一度だけ訪問し、最後に起点の頂点へ戻ってくる閉路のことです。

使用する関数とその役割

Begin
    1. 関数 isSafe()：追加しようとする頂点が、直前に追加した
       頂点と隣接しており、かつまだ追加されていないことをチェックします。
    2. 関数 hamiltonianCycle()：ハミルトン閉路問題を解決します。
    3. 関数 hamCycle()：hamiltonianCycle() を呼び出してハミルトン問題を解きます。
       ハミルトン閉路が存在しない場合は false を返し、
       存在する場合は true を返して経路を出力します。
End

アルゴリズムのポイント：バックトラッキング

このプログラムはバックトラッキング（探索の巻き戻し）という手法を採用しています。頂点0を始点として固定し（グラフが無向であるため、閉路はどの頂点から始めても構いません）、残りの頂点を一つずつ経路に追加していきます。

各ステップでは isSafe() を使って、候補の頂点が「直前の頂点と辺でつながっているか」「すでに経路に含まれていないか」を確認します。条件を満たせば経路に追加し、再帰的に次の頂点を探します。すべての頂点を配置できたら、最後の頂点から始点へ戻る辺が存在するかを確認します。途中で行き詰まった場合は、直前の選択を取り消して別の候補を試します。この処理を繰り返すことで、解が存在すれば必ず見つけ出すことができます。

なお、ハミルトン閉路問題はNP完全問題として知られており、このバックトラッキングによる解法の最悪計算量は O(N!) となります。そのため大規模なグラフには不向きですが、小規模なグラフの判定には十分有効です。

サンプルコード

#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 all vertices are included in Hamiltonian Cycle
    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)) //Check if this vertex can be added to Hamiltonian Cycle
       {
          path[pos] = n;
          //recur to construct rest of the path
          if (hamiltonianCycle (g, path, pos+1) == true)
             return true;
          path[pos] = -1; //remove vertex if it doesn't lead to the solution
       }
    }
    return false;
}
bool hamCycle(bool g[N][N])
{
    int *path = new int[N];
    for (int i = 0; i < N; i++)
       path[i] = -1;
    //put vertex 0 as the first vertex in the path. If there is a Hamiltonian Cycle, then the path can be started from any point
    //of the cycle as the graph is undirected
    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

この出力は、頂点 0 → 4 → 1 → 2 → 3 の順にすべての頂点を一度だけ訪問し、最後に再び頂点 0 へ戻ることで、ハミルトン閉路が正しく形成されていることを示しています。