Chu trình Hamilton là đường đi Hamilton sao cho có cạnh (trong đồ thị) từ đỉnh cuối đến đỉnh đầu của đường đi Hamilton. Trong đồ thị vô hướng là đường đi thăm mỗi đỉnh đúng một lần.
Hàm và mục đích
Begin 1. hàm isSafe() kiểm tra xem có kề với đỉnh vừa thêm và chưa thêm. 2. hàm hamiltonianCycle() giải bài toán Hamilton. 3. hàm hamCycle() dùng hamiltonianCycle() giải bài toán. Trả về false nếu không có chu trình Hamilton, ngược lại true và in đường đi. End
Ví dụ
#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) { //Nếu tất cả đỉnh đã trong chu trình Hamilton 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)) { //Kiểm tra đỉnh có thể thêm vào chu trình path[pos] = n; //đệ quy xây dựng phần còn lại if (hamiltonianCycle (g, path, pos+1) == true) return true; path[pos] = -1; //xóa đỉnh nếu không dẫn đến giải pháp } } return false; } bool hamCycle(bool g[N][N]) { int *path = new int[N]; for (int i = 0; i < N; i++) path[i] = -1; //đặt đỉnh 0 là đỉnh đầu tiên. Nếu có chu trình Hamilton, đường đi có thể bắt đầu từ bất kỳ điểm nào //của chu trình vì đồ thị vô hướng 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; }Kết quả
Cycle Exists: Following is one Hamiltonian Cycle 0 4 1 2 3 0