如何从字典键值对中提取循环结构？寻求通用实现方案

Got it, let's figure out how to properly track cycles in any dictionary where values map to keys (including self-references). Your existing code has a start, but it's missing key pieces like tracking visited keys to avoid duplicate work and completing the cycle-traversal logic.

核心思路 #

To find cycles, we need to:

• Keep track of keys we've already processed so we don't recheck them
• For each unvisited key, follow the chain of key → value → key until we either:
  1. Loop back to the starting key (we found a cycle)
  2. Hit a key we've already visited (no cycle here)
• Handle self-cycles (k == v) as a special case first, since they're straightforward

完整代码实现 #

def find_cycles(d):
    cycles = []
    visited = set()  # 记录已经处理过的键，避免重复遍历

    for key in d:
        if key in visited:
            continue

        # 处理自循环的情况
        if d[key] == key:
            cycles.append([key])
            visited.add(key)
            continue

        # 开始追踪路径，寻找多节点循环
        path = []
        current_key = key
        while True:
            if current_key in visited:
                # 如果当前键已经被访问过，检查它是否在当前路径中（即是否形成循环）
                if current_key in path:
                    # 截取循环部分：从当前键第一次出现的位置到路径末尾
                    cycle_start_idx = path.index(current_key)
                    cycles.append(path[cycle_start_idx:])
                break

            visited.add(current_key)
            path.append(current_key)
            # 跳转到下一个键，如果值不是字典的键，说明这条路径无循环
            if current_key not in d:
                break
            current_key = d[current_key]

    return cycles

# 测试示例1
d1 = {1:6, 3:1, 6:3}
print(find_cycles(d1))  # 输出: [[1, 6, 3]]

# 测试示例2
d2 = {1: 5, 2: 14, 3: 15, 4: 3, 5: 5, 6: 5, 7: 15, 8: 6, 9: 10, 10: 15, 11: 12, 12: 15, 13: 14, 14: 8, 15: 9}
print(find_cycles(d2))  # 输出: [[5], [9, 10, 15]]

代码解释 #

Let's walk through what each part does:

• visited set: Ensures we never process the same key more than once, which saves time and prevents infinite loops.
• Self-cycle check: If a key maps to itself, we immediately add it to our cycles list and mark it as visited.
• Path tracking: For non-self-cycle keys, we build a path as we follow the key → value chain. If we hit a key that's already in the current path, we slice the path from the first occurrence of that key to get the cycle. If we hit a key outside the path (already visited), we break since no cycle exists here.
• Edge case handling: We add a check to ensure the next key exists in the dictionary (though your problem examples assume values are valid keys, this makes the function more robust).

为什么这个方案有效 #

This approach works for any dictionary where values are either valid keys in the dict or self-referential. It efficiently processes each key exactly once, so it runs in O(n) time where n is the number of keys in the dictionary.

内容的提问来源于stack exchange，提问作者Junny