2

我想生成一个完整的无向图的所有哈密顿循环（循环和反转算作重复的集合的排列，并且被排除在外）。

例如，{1,2,3} 的排列是

标准排列：

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

我希望程序/算法为我打印的内容：

1,2,3

由于 321 只是向后 123，所以 312 只是 123 旋转了一个位置，依此类推。

我看到很多关于给定集合具有的这些循环数量的讨论，以及查找图是否具有哈密顿循环的算法，但没有关于如何在完整的无向图中枚举它们（即一组数字可以在集合中的任何其他数字之前或之后）。

我真的很想要一个算法或 C++ 代码来完成这个任务，或者如果你能指导我到哪里有关于这个主题的材料。谢谢！

4

2 回答 2

3

您可以对输出设置一些限制以消除不需要的排列。假设我们想要置换数字 1, ..., N。为了避免某些特殊情况，假设 N > 2。

为了消除简单的旋转，我们可以要求第一位是 1。这是真的，因为任意排列总是可以旋转成这种形式。

为了消除倒数，我们可以要求第二位的数字必须小于最后一位的数字。这是真的，因为从 1 开始的两个相互反转的排列中，恰好有一个具有此属性。

因此，一个非常简单的算法可以枚举所有排列并排除无效的排列。当然也有优化的可能。例如，在生成步骤中可以轻松避免不以 1 开头的排列。

于 2013-01-29T18:11:45.327 回答
0

检查路径是否与循环中不同点开始的路径相同的一种超级懒惰的方法（IE，相同循环或相同循环的反向是这样的：

1：决定按照惯例，所有循环将从最低的顶点数开始，并沿两个相邻序数中较低的方向继续。

因此，所有上述路径将以相同的方式进行描述。

第二个，其他有用的信息在这里：

如果您想检查两条路径是否相同，您可以将一条与其自身连接并检查它是否包含第二条路径或第二条路径的反向。

那是，

1 2 3 1 2 3

包含上述所有路径或其相反的路径。由于找到所有哈密顿循环的过程似乎比这个算法的效率低下要慢得多，我觉得我可以把它扔进去:)

于 2013-01-29T21:29:53.150 回答