c++算法找哈密顿图

哈密顿图是一种图，其中存在一条经过每个顶点恰好一次的路径。要找出一个有n个节点的哈密顿图需要使用NP完全问题的算法，目前还没有有效的多项式时间算法。

下面是一种基于回溯的暴力算法：

1.初始化一个空路径，该路径包含起始节点。
2.对于每个未访问的邻居节点，将其添加到路径中并标记为已访问。
3.递归地调用步骤2，直到所有节点都被访问。
4.如果路径中包含了所有的节点并且最后一个节点有一条边连接到起始节点，则找到了哈密顿图。
5.如果路径中未包含所有节点或者最后一个节点未连接到起始节点，则回溯到前一个节点并将其从路径中删除。
6.重复步骤2-5，直到找到哈密顿图或者所有路径都被尝试。

下面是一个基于邻接矩阵的C++实现：

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

bool isSafe(int v, vector<vector<int>>& graph, vector<int>& path, int pos) {
    if (graph[path[pos - 1]][v] == 0) // 该节点与前一个节点不相邻
        return false;
    for (int i = 0; i < pos; i++) // 该节点已经在路径中
        if (path[i] == v)
            return false;
    return true;
}

bool hamiltonianUtil(vector<vector<int>>& graph, vector<int>& path, int pos) {
    if (pos == graph.size()) { // 所有节点都已经在路径中
        if (graph[path[pos - 1]][path[0]] == 1) // 最后一个节点与起始节点相邻
            return true;
        else
            return false;
    }
    for (int v = 1; v < graph.size(); v++) {
        if (isSafe(v, graph, path, pos)) {
            path[pos] = v;
            if (hamiltonianUtil(graph, path, pos + 1))
                return true;
            path[pos] = -1; // 回溯
        }
    }
    return false;
}

bool hamiltonian(vector<vector<int>>& graph) {
    vector<int> path(graph.size(), -1);
    path[0] = 0;
    if (hamiltonianUtil(graph, path, 1) == false)
        return false;
    else {
        cout << "Hamiltonian Path: ";
        for (int i = 0; i < graph.size(); i++)
            cout << path[i] << " ";
        cout << path[0] << endl;
        return true;
    }
}

int main() {
    vector<vector<int>> graph = {{0, 1, 0, 1, 0},
                                 {1, 0, 1, 1, 1},
                                 {0, 1, 0, 0, 1},
                                 {1, 1, 0, 0, 1},
                                 {0, 1, 1, 1, 0}};
    hamiltonian(graph);
    return 0;
}

在上面的例子中，我们使用了邻接矩阵来表示图，其中0表示没有边相连，1表示有边相连。在主函数中，我们定义了一个5个节点的图，并调用了hamiltonian函数来查找哈密顿图。如果找到了哈密顿图，则输出路径，否则返回false。