输入 n 点 m 边，求图中的 哈密顿路径 C++代码实现

哈密顿路径是一个经典的问题，指的是在一个无向图中找到一条经过所有顶点恰好一次的路径。对于n个顶点和m条边的情况，确定是否存在哈密顿路径是NP完全问题，通常需要使用回溯算法或深度优先搜索等搜索策略。

下面是一个简单的C++代码实现，使用深度优先搜索寻找哈密顿路径。这个代码仅适用于完全图（即每对顶点间都有边相连），因为哈密顿路径在有缺失边的情况下不存在。请注意，由于复杂度原因，实际应用中这并不能保证在所有情况下都能找到解，但对于小规模问题可以尝试。

#include <iostream>
#include <vector>

// 定义图的数据结构
std::vector<std::vector<int>> adj; // 存储邻接表

bool isHamiltonianPath(int start, int end) {
    std::vector<bool> visited(n, false); // 记录已访问过的节点
    if (start == end) { // 如果起始点等于结束点，则直接返回true
        return true;
    }
    visited[start] = true;

    for (int i : adj[start]) { // 从起始节点开始遍历
        if (!visited[i]) {
            if (isHamiltonianPath(i, end)) { // 如果能找到剩余部分的路径
                visited[end] = true; // 标记当前节点已到达终点
                return true;
            }
            visited[i] = false; // 没找到合适的路径，回溯并标记节点未访问
        }
    }
    return false; // 当遍历完所有邻居均无法构成路径时，返回false
}

int main() {
    int n, m; // 图的顶点数和边数
    std::cin >> n >> m;

    // 假设输入的是一个完全图，用邻接矩阵表示
    adj.resize(n);
    for (int i = 0; i < n; ++i) {
        adj[i].resize(n, -1); // 初始化为-1表示没有边
    }

    // 输入边的信息，这里简化处理，假设直接输入两个端点
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u][v] = adj[v][u] = 1; // 表示存在边连接两点
    }

    if (adj[start][end] == 0) {
        std::cout << "No Hamiltonian path exists.\n";
    } else {
        if (isHamiltonianPath(0, n - 1)) {
            std::cout << "A Hamiltonian path exists!\n";
        } else {
            std::cout << "No Hamiltonian path found.\n";
        }
    }

    return 0;
}