Chương trình C++ kiểm tra chu trình Hamilton (Hamiltonian Cycle) hoặc đường đi Hamilton trong đồ thị

Chu trình Hamilton (Hamiltonian cycle) là đường đi Hamilton (Hamiltonian Path) sao cho có cạnh (trong đồ thị) từ đỉnh cuối về đỉnh đầu của đường đi Hamilton. Trong đồ thị vô hướng, đường đi Hamilton là đường đi thăm mỗi đỉnh đúng một lần.

Các hàm và mục đích:

Bắt đầu
  1. hàm isSafe() kiểm tra xem đỉnh có kề với đỉnh vừa thêm và chưa được thêm chưa.
  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.
Kết thúc

Ví dụ mã nguồ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) {
    // Nếu tất cả đỉnh đã nằm 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)) {
            path[pos] = n;
            // đệ quy xây dựng phần còn lại của đường đi
            if (hamiltonianCycle(g, path, pos+1) == true)
                return true;
            path[pos] = -1; // xóa đỉnh nếu không dẫn đến lời giải
        }
    }
    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 trong đường đi.
    // Nếu có chu trình Hamilton, đường đi có thể bắt đầu từ bất kỳ điểm nào
    // vì đồ thị vô hướng
    path[0] = 0;
    if (hamiltonianCycle(g, path, 1) == false) {
        cout << "\nChu trình không tồn tại" << endl;
        return false;
    }
    displaytheSolution(path);
    return true;
}

void displaytheSolution(int p[]) {
    cout << "Chu trình tồn tại:";
    cout << " Dưới đây là một chu trình Hamilton \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ả

Chu trình tồn tại: Dưới đây là một chu trình Hamilton
0 4 1 2 3 0