选择适当的算法来创建和计算元素共享对的排列
Selecting the appropriate algorithm for creating and calculating permutations of element-sharing pairs
我对执行以下任务的时间复杂度最低的算法感兴趣：
给定一个元组列表，例如[(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], 其中 start 和 end 具有相同的字母并且通过连接至少共享一个的对形成元组的元素。注意：(A, B) 被认为与 (B, A) 相同，就像 (A, C) 与 (C, A) 相同，因此它可用于创建两个对 (C, B, A, C) 或 (A, B, C, A )
重要的约束是对长度有限制。例如。确保序列不超过 7 个元素。
我试图通过每次扩展树一个元素直到达到最大长度 7 来解决这个问题，但我很好奇是否有更好的方法来解决这个问题。非常感谢，期待听到您的好主意！
时间复杂度
解决此问题的任何算法的（最坏情况）时间复杂度的下限为 O(n)，其中 n 是图的边数（即元组）：
- 如果您需要找到从 A 到 A 的 所有 个循环，您不能排除查看某个边缘，因为它很可能是一个这样的循环的一部分。
- 如果您需要找到从 A 到 A 的 any 个循环，您可能会遇到只有一个这样的循环的情况，在最坏的情况下您可能发现您访问的最后一个边缘是关闭循环的边缘。
所以在任何一种情况下，您（可能）都需要至少查看每条边一次。
算法
本质上有两种策略：广度优先或深度优先搜索。两者的时间复杂度都是 O(n).
您尝试过的算法似乎是广度优先搜索。当您需要找到最短循环时，这是更好的选择，因为这样您可以在找到循环（A-to-A）时立即退出算法。
深度优先搜索也是一个可行的选择，当然是在对循环长度设置了限制的情况下。在那种情况下，space 复杂度是 O(m)，其中 m 是一个周期的最大长度。根据图表（它的大小，它的平均分支因子），这可能比广度优先搜索所需的 O(n) space 便宜得多。
另外，广度优先搜索需要不断切换状态，而递归和回溯（深度优先搜索的特征）中发生的转换往往更容易处理。
准备工作
无论您使用哪种策略，请确保首先为图形创建一个高效的数据结构。
由一对数组组成的简单数据结构（如您的问题中所述）不够好。为了达到最优的时间复杂度，你需要建立一个邻接表（或类似的东西），这样你就可以在常数时间内找到一个节点的邻居（通过一个元组可达）。
我对执行以下任务的时间复杂度最低的算法感兴趣：
给定一个元组列表，例如[(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], 其中 start 和 end 具有相同的字母并且通过连接至少共享一个的对形成元组的元素。注意：(A, B) 被认为与 (B, A) 相同，就像 (A, C) 与 (C, A) 相同，因此它可用于创建两个对 (C, B, A, C) 或 (A, B, C, A )
重要的约束是对长度有限制。例如。确保序列不超过 7 个元素。
我试图通过每次扩展树一个元素直到达到最大长度 7 来解决这个问题，但我很好奇是否有更好的方法来解决这个问题。非常感谢，期待听到您的好主意！
时间复杂度
解决此问题的任何算法的（最坏情况）时间复杂度的下限为 O(n)，其中 n 是图的边数（即元组）：
- 如果您需要找到从 A 到 A 的 所有 个循环，您不能排除查看某个边缘，因为它很可能是一个这样的循环的一部分。
- 如果您需要找到从 A 到 A 的 any 个循环，您可能会遇到只有一个这样的循环的情况，在最坏的情况下您可能发现您访问的最后一个边缘是关闭循环的边缘。
所以在任何一种情况下，您（可能）都需要至少查看每条边一次。
算法
本质上有两种策略：广度优先或深度优先搜索。两者的时间复杂度都是 O(n).
您尝试过的算法似乎是广度优先搜索。当您需要找到最短循环时，这是更好的选择，因为这样您可以在找到循环（A-to-A）时立即退出算法。
深度优先搜索也是一个可行的选择，当然是在对循环长度设置了限制的情况下。在那种情况下，space 复杂度是 O(m)，其中 m 是一个周期的最大长度。根据图表（它的大小，它的平均分支因子），这可能比广度优先搜索所需的 O(n) space 便宜得多。
另外，广度优先搜索需要不断切换状态，而递归和回溯（深度优先搜索的特征）中发生的转换往往更容易处理。
准备工作
无论您使用哪种策略，请确保首先为图形创建一个高效的数据结构。
由一对数组组成的简单数据结构（如您的问题中所述）不够好。为了达到最优的时间复杂度，你需要建立一个邻接表（或类似的东西），这样你就可以在常数时间内找到一个节点的邻居（通过一个元组可达）。