数据结构：哈密顿回路基础

本文主要是介绍数据结构：哈密顿回路基础，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么是哈密顿回路？

哈密顿回路（Hamiltonian Cycle）是图论中的一个概念，指的是在一个图中通过图的每个顶点恰好一次且仅一次，并最终回到起始顶点的闭合回路。在一个哈密顿回路中，除了起始和结束的顶点必须是同一个顶点，并且这个顶点恰好出现两次之外，其他每个顶点都恰好出现一次。哈密顿回路的命名来自于爱尔兰数学家威廉·罗伊兰·哈密顿。

判断是否存在哈密顿环问题是一个经典的NP完全问题，这意味着目前没有已知的多项式时间算法能解决所有情况。对于一个含有 $V$ 个顶点和 $E$ 条边的图来说，常见的算法时间复杂度如下：

暴力搜索法：尝试图中所有可能的顺序来查找哈密顿环。其时间复杂度为 $O (V!)$ ，因为需要检查每个顶点的所有排列。
回溯法：在搜索过程中，如果路径不满足条件，则回退一步。这是一种改进的暴力法，但最坏情况的时间复杂度仍然为 $O (V!)$ 。
动态规划（例如 Held-Karp 算法）：用于求解旅行商问题（TSP），该问题与哈密顿环问题紧密相关。Held-Karp算法使用动态规划，其时间复杂度为 $O(V^2 2^V)$ 。
启发式算法：如遗传算法、蒙特卡洛方法等，并不保证总是能找到解决方案，但在一些情况下它们可以在多项式时间内给出近似解。时间复杂度因算法和实现而异，但通常比 $O(V^2 2^V)$ 要低。

判断给路径是否是哈密顿回路

只需要满足条件：每个点经过一次，并且是一个环路就行。像判断是否是给定图的拓扑排序一样，按照流程走一遍就行。
优化代码：

尽量不适用全局变量，使用引用传参。
将条件合并。

#include <iostream>
#include <vector>
#include <unordered_set>using namespace std;bool isHamiltonianCycle(const vector<unordered_set<int>>& graph, const vector<int>& path) {if(path.front() != path.back() || path.size() != graph.size()) {return false;}unordered_set<int> visited;int len=path.size();for(int i = 0; i < len - 1; ++i) {if(graph[path[i]].count(path[i+1]) == 0 || visited.count(path[i]) != 0) {return false;}visited.insert(path[i]);}if(graph[path[len-2]].count(path.back()) != 0)return true;else return false;
}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int N, M;cin >> N;vector<unordered_set<int>> graph(N + 1);cin >> M;while(M--) {int u, v;cin >> u >> v;graph[u].insert(v);graph[v].insert(u);}int K;cin >> K;while(K--) {int n, v;cin >> n;vector<int> path;path.reserve(n);//无所谓，这改变的是capacity，与resize不一样。while(n--) {cin >> v;path.emplace_back(v);}if(isHamiltonianCycle(graph, path)) {cout << "YES\n";} else {cout << "NO\n";}}return 0;
}