โปรแกรม C++ ตรวจสอบ Hamiltonian Cycle หรือ Path ในกราฟ

Hamiltonian cycle คือ Hamiltonian Path ที่มีขอบ (ในกราฟ) จากโหนดสุดท้ายไปโหนดแรกของ Hamiltonian Path ใน undirected graph เป็น path ที่เยี่ยมชมแต่ละโหนดของกราฟครั้งเดียวพอดี

ฟังก์ชันและวัตถุประสงค์

Begin
  1. function isSafe() ตรวจสอบว่าติดกับโหนดที่เพิ่มไปก่อนหน้า และยังไม่ถูกเพิ่ม
  2. function hamiltonianCycle() แก้ปัญหา hamiltonian
  3. function hamCycle() ใช้ hamiltonianCycle() แก้ปัญหา
     คืนค่า false ถ้าไม่มี Hamiltonian Cycle เป็นไปได้ มิฉะนั้น true และพิมพ์ path
End

ตัวอย่างโค้ด

#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;
  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