python - 选择适当的算法来创建和计算元素共享对的排列

Question

我对执行以下任务的时间复杂度最低的算法感兴趣:

给定一个元组列表，例如 [(A, B), (B, C), (C, D), (D E), (A, D), (E, A), (A, C )], 查找诸如 [A, B, C, D, E, A] 或 [A, D, C, B, >A]，它们以相同的字母开始和结束，并且通过连接共享元组中至少一个元素的对形成。注意:(A, B) 被认为与 (B, A) 相同，就像 (A, C) 与 (C, A) 相同，因此它可用于创建两个对 (C, B, A, C) 或 (A, B, C, A)

重要的约束是对长度有限制。例如。确保序列不超过 7 个元素。

我试图通过每次扩展树一个元素直到达到最大长度 7 来解决这个问题，但我很好奇是否有更好的方法来解决这个问题。非常感谢并期待听到您的好主意!

Answer 1

时间复杂度

解决此问题的任何算法的(最坏情况)时间复杂度的下限都是 O(n)，其中 n 是边数 (即图的元组):

• 如果您需要找到从 A 到 A 的所有个循环，您不能排除寻找某个边缘，因为它很可能是一个这样的循环的一部分。
• 如果您需要找到从 A 到 A 的任何个循环，您可能会遇到只有一个这样的循环的情况，在最坏的情况下，您可能会发现最后一个边您访问的是结束循环的那个。

因此在任何一种情况下，您(可能)都需要至少查看每条边一次。

算法

本质上有两种策略:广度优先或深度优先搜索。两者的时间复杂度均为 O(n)。

您似乎尝试过的算法是广度优先搜索。当您需要找到最短循环时，这是更好的选择，因为一旦找到循环(A-to-A)，您就可以退出算法。

深度优先搜索也是一个可行的选择，当然是在对循环长度设置了限制的情况下。在这种情况下，空间 复杂度为O(m)，其中m 是循环的最大长度。根据图形(它的大小、它的平均分支因子)，这可能比广度优先搜索所需的 O(n) 空间便宜得多。

此外，广度优先搜索需要不断切换状态，而递归和回溯(深度优先搜索的特征)期间发生的转换通常更容易处理。

准备工作

无论您使用哪种策略，请确保首先为图创建一个高效的数据结构。

由一对数组组成的简单数据结构(如您的问题中所述)不够好。为了实现最佳时间复杂度，您需要构建一个邻接表(或类似的东西)，以便您可以在恒定时间内找到一个节点的邻居(通过一个元组可达)。