如何使用BFS在图中找到哈密顿环？ （条件是图形完全是哈密顿图）

Question

我正在尝试解决哈密顿循环问题。

我的任务条件是：

该小组由N人组成。在其中，每个人都有N / 2个朋友。友谊是对称的（如果A是朋友B，那么B是朋友A）。小组中的一个人有一本书（他的数字X），每个人都想读一本书，然后与其他人讨论。

[确定书的传输方式的方法是，书将只拜访每个人一次，仅在一个朋友之间传递，最后返回给它的所有者。

也就是说，它满足狄拉克定理的条件。

在小图my solutions上正常工作，但是在大图上，我的解决方案给出了时间限制例外。

有什么方法可以比O（n！）更快地解决它？

Answer 1

[有一个多项式时间算法可以在每个顶点度至少为N / 2的图中找到哈密顿循环。

在"A Simple Extension of Dirac’s Theorem on Hamiltonicity" Yasemin Büyükçolak, Didem Gözüpek, Sibel Özkan, Mordechai Shalom中有描述。