哈密顿回路算法c++

以下是一个使用C++实现的哈密顿回路算法的示例：

#include <iostream>
#include <vector>
using namespace std;

bool hamiltonianPath(vector<vector<int>>& graph, vector<int>& path, vector<bool>& visited, int curr, int n) {
    if (path.size() == n) {
        if (graph[curr][0] == 1) {
            return true;
        }
        return false;
    }

    for (int i = 0; i < n; i++) {
        if (graph[curr][i] == 1 && !visited[i]) {
            visited[i] = true;
            path.push_back(i);

            if (hamiltonianPath(graph, path, visited, i, n)) {
                return true;
            }

            visited[i] = false;
            path.pop_back();
        }
    }

    return false;
}

bool hasHamiltonianPath(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> path;
    vector<bool> visited(n, false);

    visited[0] = true;
    path.push_back(0);

    return hamiltonianPath(graph, path, visited, 0, n);
}

int main() {
    int n;
    cout << "Enter the number of vertices: ";
    cin >> n;

    vector<vector<int>> graph(n, vector<int>(n, 0));

    cout << "Enter the adjacency matrix: " << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    if (hasHamiltonianPath(graph)) {
        cout << "The graph has a Hamiltonian path." << endl;
    } else {
        cout << "The graph does not have a Hamiltonian path." << endl;
    }

    return 0;
}