有人可以把我介绍给汉密尔顿循环吗？

Question

我有这个项目,我必须提出实现哈密顿循环的Java源代码.我在谷歌搜索,至少现在我知道汉密尔顿循环是什么,除了起始顶点之外只穿过所有顶点的路径,因为它也是最后一个顶点(告诉我,如果我错了).问题是我不知道如何实现它.基本上,我的问题是:

1. 如何,你在哪里实现汉密尔顿循环？
2. 哈密​​顿循环的应用是什么(这有助于理解为什么它如此重要)

Answer 1

1. 您没有实现哈密顿循环，而是找到它（或者发现给定的图表不存在）。由于这是一个 NP 完全问题，这意味着这可能不是有效的解决方案，因此我只实现一个简单的回溯算法。由于您正在寻找一个循环，因此从哪个节点开始并不重要。
2. 哈密​​顿循环可用于密码学中的零知识证明。我不确定这是否仍然只是研究，或者是否正在任何加密协议中积极使用。