1

我终于设法编写了一个代码来识别当前配置可能出现的所有循环。例如，对于下图，以下是我的程序的输入。

图问题

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()

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

这是结果：

starting search from 1
--------------------------------------------------------
the loop is complete [1, 2, 3, 1]
the loop is complete [1, 2, 3, 4, 1]
the loop is complete [1, 2, 4, 1]
the loop is complete [1, 2, 4, 3, 1]
the loop is complete [1, 3, 2, 1]
the loop is complete [1, 3, 2, 4, 1]
the loop is complete [1, 3, 4, 1]
the loop is complete [1, 3, 4, 2, 1]
the loop is complete [1, 4, 2, 1]
the loop is complete [1, 4, 2, 3, 1]
the loop is complete [1, 4, 3, 1]
the loop is complete [1, 4, 3, 2, 1]
--------------------------------------------------------
starting search from 2
--------------------------------------------------------
the loop is complete [2, 1, 3, 2]
the loop is complete [2, 1, 3, 4, 2]
the loop is complete [2, 1, 4, 2]
the loop is complete [2, 1, 4, 3, 2]
the loop is complete [2, 3, 1, 2]
the loop is complete [2, 3, 1, 4, 2]
the loop is complete [2, 3, 4, 1, 2]
the loop is complete [2, 3, 4, 2]
the loop is complete [2, 4, 1, 2]
the loop is complete [2, 4, 1, 3, 2]
the loop is complete [2, 4, 3, 1, 2]
the loop is complete [2, 4, 3, 2]
--------------------------------------------------------
starting search from 3
--------------------------------------------------------
the loop is complete [3, 1, 2, 3]
the loop is complete [3, 1, 2, 4, 3]
the loop is complete [3, 1, 4, 2, 3]
the loop is complete [3, 1, 4, 3]
the loop is complete [3, 2, 1, 3]
the loop is complete [3, 2, 1, 4, 3]
the loop is complete [3, 2, 4, 1, 3]
the loop is complete [3, 2, 4, 3]
the loop is complete [3, 4, 1, 2, 3]
the loop is complete [3, 4, 1, 3]
the loop is complete [3, 4, 2, 1, 3]
the loop is complete [3, 4, 2, 3]
--------------------------------------------------------
starting search from 4
--------------------------------------------------------
the loop is complete [4, 1, 2, 3, 4]
the loop is complete [4, 1, 2, 4]
the loop is complete [4, 1, 3, 2, 4]
the loop is complete [4, 1, 3, 4]
the loop is complete [4, 2, 1, 3, 4]
the loop is complete [4, 2, 1, 4]
the loop is complete [4, 2, 3, 1, 4]
the loop is complete [4, 2, 3, 4]
the loop is complete [4, 3, 1, 2, 4]
the loop is complete [4, 3, 1, 4]
the loop is complete [4, 3, 2, 1, 4]
the loop is complete [4, 3, 2, 4]
--------------------------------------------------------

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

感谢您提供的一个答案，该答案表明重复循环具有在反转时保持不变的特性。例如：

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

如果在上述情况下它从与第一个和第二个相同的顶点开始，反转将表明它们是相同的循环，但在第三种情况下，虽然它与前两个相同，但情况有点棘手。现在应该通过该循环中的第三个顶点进行反向操作。当形成循环的顶点数量增加时，这种复杂性会增加。因此，有什么算法可以有效地简化这个问题？我在这里看到了一些递归模式，但它仍然有点复杂，并且会撒谎以知道是否有人可以提出简单的解决方案。

4

2 回答 2

2

请注意，循环副本的属性是，如果您颠倒它的顺序，您将获得原始循环。

为了让您的生活更轻松，您可以决定将具有较小词典索引的循环用于您的解决方案。这意味着，如果您找到循环1->3->2->1和1->2->3->1（根据您的定义相等），您将采用1->2->3->1解决方案。

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

您可以通过一种非常简单的方法来查看字典索引，只需创建一个不符合顶点顺序的数字即可。

例如：翻译1->2->3->1为1231和1->3->2->1。小于，因此将被用于解决方案并被忽略。1321123113211->2->3->11->3->2->1

编辑：

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

于 2013-11-08T15:27:56.843 回答
1

在确保拥有循环之后，一种简单的方法是创建一组frozensets。

>>> 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])])

这当然会迫使您假设 freezeset 中的第一项是开始和结束顶点。

于 2013-11-08T15:47:11.170 回答