在闭图中寻找唯一环

Question

最后，我设法编写了一个代码来识别当前配置中所有可能的循环。例如，对于下面的图像，下面是我的程序的输入。在

network2=Pipes.NetworkManager(vertices=[1,2,3,4],
                 nodes=[(1,2),(1,3),(1,4),(2,1),(2,3),
                        (2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)])

network2.search_loop()

现在，我很难从输出中过滤数据以找到唯一的循环。在

结果是：

^{pr2}$

还有什么更好的选择解决问题。现在在我得到结果之后，我发现很难过滤这些结果并找到唯一的循环。我对图论的理解是有限的（我刚开始读）。从已识别的循环中找到唯一循环的有效方法是什么？在

感谢您给出的一个答案，即重复循环具有在反转时保持不变的特性。例如：

[1,2,3,1]
[1,3,2,1]
[2,3,1,2]

如果在上面的例子中，第一个和第二个从同一个顶点开始，反转将表明这些是相同的循环，但是在第三个情况下，尽管它与前两个是相同的循环，但情况并不复杂。现在反过来应该通过循环中的第三个顶点来完成。当形成循环的顶点的数目增加时，这种复杂性会增加。因此，有什么算法可以有效地简化这个问题？我在这里看到了一些递归模式，但它仍然有点复杂，如果有人能提出简单的解决方案，我会撒谎。在

Answer 1

一个简单的方法是创建一组冻结集，在您可以确保您拥有循环之后。在

>>> loop1 = [1,2,3,4,1]
>>> loop2 = [1,2,4,3,1]
>>> loop3 = [1,2,3,1]
>>> loops = [loop1,loop2,loop3]
>>> loops = set([frozenset(loop) for loop in loops])
>>> loops
set([frozenset([1, 2, 3, 4]), frozenset([1, 2, 3])])

当然，这会迫使您假设冻结集中的第一个项是起点和终点顶点。在

Answer 2

请注意，循环复制具有这样的属性：如果颠倒其顺序，则将获得原始循环。在

为了让你的生活更轻松，你可以决定你将使用字典索引较少的循环作为你的解决方案。这意味着，如果找到循环1->3->2->1和{}（它们在您的定义中是相等的），那么您将把1->2->3->1带到解决方案中。在

从这一点开始，最好的方法是反转找到的每个循环，如果反向模式的字典索引比原始模式低，则忽略该循环。否则将其添加到解决方案中。在

你可以用一个非常简单的方法来检查字典索引，只需按照顶点的顺序创建一个数字。在

例如：将1->2->3->1转换为1231，并将1->3->2->1转换为1321。1231小于1321，因此{}将被带到解中，{}将被忽略。在

编辑：

为了消除不共享同一起始点的重复循环（例如在您的示例中，1->3->2->1和{}），您可以忽略第一个顶点索引不是循环中最小索引的任何循环。这里2->1->3->2可以忽略，因为索引2不是循环中最小的。在